Lt;г,4/>0.

Со второй группой неравенств

поступаем аналогично. Переносим р_] вправо и делим на д₇- < 0; при этом смысл неравенства меняется на противоположный. По­лучаем

Чтобы удовлетворялось каждое неравенство второй группы, / надо определять по наименьшему из найденных значений:

/< Ш1П

' Р^Л

Ч)

Lt; 0.

Объединяя оба результата в один, имеем

тах

V

Л Ъ)

Gt; 0

Г Е?

д^< 0

Таким образом, для положительных коэффициентов д, пара-

метр ( должен быть больше наибольшего отношения

Ч)

отрицательных — меньше наименьшего. Если все коэффициенты < 7у одного знака, то вторым концом интервала изменения пара­метра является бесконечность соответствующего знака. Если < 7у = 0, то из условия следует, что в данном столбце р^> 0 и

ц + д/=Р; +0-(= Р_]> 0

для любого {. Поэтому такой столбец можно не принимать во внимание.

Отыскав правую границу а! изменения параметра (левой гра­ницей на первом этапе всегда служит значение а), сравниваем интервал [а, а^ с заданным интервалом [а, Р]. Если первый из

них больше, то задача решена: на всем отрезке [а, (3] найденное решение оптимально. Если же интервал [а, 0ц] меньше заданно­го, то исключаем его из рассмотрения, а для оставшегося отрезка [а_ь (3] задачу решаем заново. Так этап за этапом будут найдены все оптимальные планы.

Рассмотрим пример (решение и исходные данные И. Ф. Полу­нина). Необходимо решить задачу параметрического программи­рования для целевой функции

2Г_Г = (6 — 1)Х[ + (3 — 2{)х₂ + /х₃ -» тах,

в которой / изменяется на отрезке [1; 3, 5], и ограничений

XI + 2х₂ + хз< 3; 2х[ — х₂ + Зх₃ < 7; х, -> 0, У= 1, 2, 3.

Полагаем 1= 1 и получаем целевую функцию с постоянными коэффициентами

2, — 5х\ + х₂ + хз -> тах.

Составляем исходную жорданову таблицу, в которую заносим все нужные величины с учетом того, что верхним переменным Ху приписан знак «минус» (табл. 132).

132. Исходная таблица

План Х\ — х₂ = х₃ = 0 опорный, но не оптимальный. Выбираем в первом столбце разрешающий элемент и делаем шаг модифи­цированных жордановых исключений, преобразуя по общим правилам все элементы таблицы. Получаем таблицу 133, в 1_{- строке которой стоят только положительные числа. Следователь­но, для /= 1 план X! = 3, х₂ = х₃ = 0 оптимальный.

133. Первый оптимальный план

Найдем другие значения I, для которых этот план останется оптимальным. Обращаясь к последней строке таблицы 133, ви­дим, что в ней стоят два отрицательных числа и нуль (свободный член не считается). Для первого и третьего столбцов вычисляем

отношения

-1

=3.

Второй столбец с нулевым коэффициентом # пропускаем. Со­гласно формуле

(< тт

с \

И

Lt; 0

имеем

/< тт(6; 3).

Вторым концом интервала будет — °°. Следовательно, —оо< /< 3. Однако нас интересует отрезок числовой оси, начинающийся с 1, поэтому план в таблице 133 оптимален для 1 < /< 3.

Указанный отрезок [1; 3] меньше заданного [1; 3, 5]. Исключив его, продолжаем решение задачи для оставшегося интервала [3; 3, 5].

Вычислим для (= 3 коэффициенты функционала гз, выражен­ного через набор верхних переменных в таблице 133. Для этого умножим на 3 коэффициенты последней строки (включая сво­бодный член) и сложим их с коэффициентами предпоследней; результаты запишем в строку гз, которая займет место строки г\- Прочие элементы таблицы оставим без изменения; получим таб­лицу 134.

134. Промежуточный опорный план

В третьем столбце, по которому вычислено 1=3, в гз-строке получен нуль. При малейшем увеличении параметра свыше 3 на месте нуля окажется отрицательное число; план перестанет быть

оптимальным. Поэтому принимаем третий столбец за решающий элемент и делаем следующий шаг модифицированных исключе­ний (табл. 135).

135. Последний оптимальный план

В новой таблице гз-строка осталась без изменения; план х_{ = 2, х₂ - 0, х₃ = 1 оптимален. Найдем для него возможные зна­чения параметра /.

В последней строке таблицы 135 имеются как положительные, так и отрицательные коэффициенты ^. Для положительного ко­эффициента 2 по формуле

тах

V

Р?

<? у

> *, Я]> 0

имеем

-6 — тг-⁽г или 3 < /.

Для отрицательных коэффициентов согласно формуле

/< 1ШП

, #, < 0, находим
V V). ( 18 3

^^тт[-15^: -Ч0 *< 3, 6.

Объединяем оба результата в одно выражение:

3< Г< 3, 6.

Найденный отрезок [3; 3, 6] больше заданного [3; 3, 5], поэтому задача решена окончательно. При \< 1< Ъ оптимально первое найденное решение, при 3 < 1< 3, 5 — второе. Характерно, что при /= 3 оптимальны оба эти решения, а также некоторые их комби­нации.

18.3. СТОХАСТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Задачи математического программирования, в которых все или некоторые параметры являются случайными величинами и

задаются вероятностными характеристиками, называются стоха­стическими.

Такие задачи изучает самостоятельный раздел математическо­го программирования — стохастическое программирование.

Ранее, при изучении методов линейного программирования, мы исходили из допущения, что все параметры экономико-мате­матических моделей (коэффициенты целевой функции, технико-экономические коэффициенты, объемы ресурсов) являются де­терминированными, то есть определенными, точными, заранее известными. При решении землеустроительных задач, связанных с организацией сельскохозяйственного производства и террито­рии, это допущение оказывается недостаточно строгим, так как многие параметры задач, связанные с погодными условиями (осадками, температурой, инсоляцией и т.д.), а также с динами­кой цен на рынке, носят вероятностный (стохастический) харак­тер. То есть при экономико-математическом моделировании приходится работать не только с приближенными, но и со слу­чайными величинами, которые возникают как в результате дей­ствия неконтролируемых природных и экономических факторов, так и вследствие работы с информацией, искаженной в процессе ее получения и обработки.

Стохастическое программирование позволяет выбрать наилуч­ший план с точки зрения всех возможных случайных факторов.

Один из крупнейших специалистов в области исследования операций Г. Вагнер писал, что интерес к стохастическим явлени­ям был бы весьма ограничен, если бы его не стимулировала прак­тическая необходимость решения конкретных задач организаци­онного управления (Вагнер Г. Основы исследования опера­ций. — М.: Мир, 1973).

Обратимся к классической математической формулировке об­щей задачи линейного программирования в матричной форме.

Необходимо найти Р(х) = Сх —> тах при условиях Ах < В и х> 0.

В этой модели матрица А, векторы В и С являются детермини­рованными. В стохастических задачах А, В я С могут быть слу­чайными. При этом значение целевой функции Р(х) также явля­ется случайной величиной.

Для того чтобы понять значение стохастического програм­мирования для экономики сельскохозяйственного предприя­тия и его отличие от детерминированных задач, рассмотрим один из примеров, приводимых в изданной в 1972 г. в Амстер­даме монографии Д. К. Сенгунты (Зегщшйа I. К. §1оспа$ис рго§гаттт§ теШоёз апс! аррНсагюпв. — Ат$1егс! ат, N01111 НоПапй, 1972).

В задаче определялось оптимальное сочетание отраслей про­изводства (картофеля, зерна, мяса, осенней капусты) при огра ничейных ресурсах земли, капитала и труда. В качестве целевой

функции отыскивалось максимальное ожидаемое значение при­были, которая содержала стохастические параметры. Предпола­галось, что система ограничений данной задачи (Ах< В) была де­терминирована.

После преобразования целевой функции и приведения ее к детерминированному виду она приобрела следующий вид:

где т — среднее значение вектора чистого дохода; т' — транспонированный век­тор т; V— ковариационная матрица; х — вектор независимых переменных, обо­значающий объем продукции (картофель, зерно, мясо, осенняя капуста); а —ко­эффициент, показывающий степень риска.

В уравнении целевой функции первое слагаемое представляет собой величину прибыли, которую можно было бы получить при отсутствии влияния на нее случайных факторов. В детерминиро­ванной задаче целевая функция состояла бы только из первого слагаемого.

Второе слагаемое

х'Ух показывает, на сколько изменится

прибыль с учетом в модели случайных величин. С введением вто­рого слагаемого функция Р{х) приобретает нелинейный (квадра­тичный) характер.

Модель была реализована автором при следующих числовых значениях параметров:

1250'

т'=(100, 100, 100, 100); 5= (60, 60, 24, 12, 0, 799, 867, 783);

А=

' 1, 199 1, 382 2, 776 0

0 1, 382 2, 776 0, 482

1, 064 0, 484 0, 038 0

-2, 064 0, 020 0, 107 0, 229
-2, 064-1, 504-1, 145-1, 229

5, 276 4, 836 0 0

2, 158 4, 561 0 4, 198

0 4, 146 0 13, 606

" 7304, 69 903, 89 -688, 73 -1862, 05" 620, 16 -471, 14 110, 43 1124, 64 750, 69 3689, 53 _

Результаты расчета вероятностного и детерминированного ва­риантов оптимального плана приводятся в таблице 136.

Вероятностный и детерминированный планы

Переменные величины

Из таблицы видно, что при учете вероятностного характера вектора выпуска х ожидаемый чистый доход уменьшается по сравнению с детерминированным аналогом примерно на 20 %, но возрастает гарантия получения этого дохода. Коэффициент вариации для вероятностной модели К_{в в} = 30, 4%, для детер­минированной У_ЯВ=46, 2 %. Очевидно, что для собственника земли лучше иметь меньший, но устойчивый доход, что обеспе­чит стабильность производства и его гарантированную эффек­тивность.

Классификация задач и методов стохастического программиро­вания. В настоящее время разработано большое число матема­тических моделей задач стохастического программирования, что требует их классификации. В агроэкономических исследо­ваниях наиболее распространенной является классификация стохастических оптимизационных моделей, разработанная Ю. И. Копенкиным, которая не претерпела существенных из­менений с середины 70-х годов до настоящего времени (Крав-

ченко Р. Г. Математическое моделирование экономических про­цессов в сельском хозяйстве. — М.: Колос, 1978. — С. 407—411; Математическое моделирование экономических процессов в сельском хозяйстве/ Под ред. А. М. Гатаулина. — М.: Агропром-издат, 1990.-С. 384-389).

Согласно этой классификации стохастические модели задач делятся на два основных класса: одноэтапные и двухэтапные.

Одноэтапные задачи характеризуются тем, что принимается только одно решение (априорное), которое затем не корректиру­ется. Это решение имеет вид детерминированного вектора:

х = (хь х₂,..., х„).

Оно не поддается корректировке при уточнении производ­ственной ситуации. Например, априорным (предварительным) может быть решение, которое получают при усредненных значе­ниях случайных параметров.

Двухэтапные задачи основаны на применении двух последова­тельно получаемых решений. На первом этапе определяется ап­риорное (предварительное) решение, которое уточняется на вто­ром этапе в зависимости от изменения параметров случайных ус­ловий производства (исходов).

Решение, получаемое на втором этапе, называется апостери­орным. В моделях эти решения имеют вид стохастического век­тора у_г = (у\_г, У2г, Укг)> применяемого с вероятностью р_п где г— номер исходов (реализации случайных условий, г= 1, 2,..., Л).

Термин «двухэтапная задача» имеет условный характер, так как разделение на этапы относится лишь к ее постановке. С точ­ки зрения математического программирования это единственная задача, включающая одновременно переменные двух этапов, объединенные единой целевой функцией и системой ограниче­ний.

В настоящее время выделяют следующие постановки одно-этапных задач стохастического программирования.

1. Примитивная постановка задачи заключается в определении оптимального плана на основе решения обычной детерминированной задачи линейного программирования, коэф­фициенты которой рассчитаны путем усреднения случайных па­раметров и считаются условно детерминированными.

Если случайным является только вектор (О-коэффициентов целевой функции, то для решения задачи достаточно заменить

коэффициенты с, - их средними значениями су. Тогда целевая функция задачи примет вид

Р(х)=М{Сх)= М(Сх)-> тах,

где М— символ математического ожидания эффекта.

2. Жесткая постановка задачи требует, чтобы при любых конкретных реализациях (исходах) случайных параметров выполнялись все ограничения, то есть

А_гх < Д.для всех ге Я; х> 0;

Р{х)=Сх-^тзх,

где г — индекс возможной реализации (исхода) случайных параметров задачи; К — множество значений г, С — вектор средних значений целевой функции.

Таким образом, решение одноэтапной стохастической задачи сводится к решению громоздкой детерминированной задачи ли­нейного программирования при условиях:

А_{х< В_у А₂х< В₂

Арс< В_г

А^х < 5дг х> 0

и целевой функции Р(х)=Сх-> тах,

где г — номер возможной комбинации значений А и В, появляющихся с некоторой вероятностью (г= 1, 2,..., Л^.

Исходя из этого следует, что решение данной задачи в стохас­тической постановке может быть сведено к задаче линейного программирования с «пессимистическими» значениями, то есть наихудшими величинами параметров технико- экономических коэффициентов и объемов ограничений.

Жесткая постановка должна применяться тогда, когда нужно исключить риск. Этого требуют ситуации, когда выполнение хотя бы одного из ограничений задачи приводит к катастрофическим последствиям (например, к разорению и ликвидации сельскохо­зяйственного предприятия).

3. Вероятностная постановка задачи (с вероятностными ограничениями) — вероятность выполнения /-го

ограничения должна быть не менее заданной величины й}'', то есть:

Г0

> А^(/\0< А^(/)< 1, /=1, 2...... /я.

Задача с вероятностными ограничениями обычно решается для ситуаций, когда случайным является вектор В, а матрица А и вектор С — детерминированы.

Эта задача может быть также сведена к детерминированной задаче линейного программирования следующего вида:.

Р(х)=Сх-^тах, Ах< В, х> 0.

Элемент случайного вектора В=Ь^1=1, 2,..., т) вычисляют по уравнению вида

Ь; где ф/(6,) — плотность распределения случайной величины Ь₁.

Если Р^-\, данная постановка переходит в жесткую.

Методы постановки двухэтапных задач стохастического про­граммирования делятся на непрямые и прямые.

Непрямыми методами стараются свести зависимость Р(х, со), где со —вероятностный элемент, к зависимости Р(х), а затем применить один из известных методов математического программирования. Иными словами, стохастическую задачу сво­дят к ее детерминированному аналогу, а последний решают изве­стными методами линейного или нелинейного программирова­ния.

К прямым методам относят методы, основанные на ин­формации только о функции Р(х, со): методы стохастической ап­проксимации, проектирования стохастических квазиградиентов и др. (Ермольев Ю. М. Стохастические модели и методы оптими­заций. — Киев: Кибернетика, 1974. — № 4).

Рассмотрим рекомендуемые непрямые приемы сведения двухэтапных стохастических задач к задачам линейного про­граммирования (Копенкин Ю. И. Стохастические задачи мате­матического программирования. — В кн.: Математическое мо­делирование экономических процессов в сельском хозяйстве/ Под ред. А. М. Гатаулина. — М.: Агропромиздат, 1990. — С. 388—389).

1. Если случайным является вектор В (свободные члены ограничений Ь_ь обозначающие наличие ресурсов), а матрица А детерминированная, то двухэтапная стохастическая поста­новка допускает возникновение невязок в ограничениях (не­хватку ресурсов) при отдельных исходах, однако им соответ­ствует определенный штраф, который вычитается из целевой функции. Задача линейного программирования при этом имеет вид

Ах -В^

Ах +Ду1 =5₁

Ах +ДУ2 =^2

Ах +Оух=Вх

х> 0, _У1> 0,..., у_м> 0 Р{х, у) = Сх + р₁уу₁ + р₂уу₂ +... + р_муу_м,

где х = {х\, х₂,..., х„) — вектор основных переменных (управляющих переменных первого этапа); у_г = {у_Хп у_2г,..., у_тг] — вектор вспомогательных переменных (управ­ляющих переменных второго этапа), обозначающих невязки в /-м ограничении при г-м исходе (/- = 1, 2,..., ЛО; В_г = {Ь_1п Ь_2п..., Ь_тг) — вектор свободных членов ограни­чений, обозначающих наличие /-го ресурса при г-м исходе (г = 1, 2,..., ЛО; А — мат­рица размерностью тп неизменяющихся технико-экономических коэффициентов ау, обозначающих затраты /-го ресурса за единицу у-го вида деятельности; О — вспомогательная матрица, элементы которой служат для ввода в ограничения невя­зок (например, диагональная матрица, элементы главной диагонали которой равны —1); У ⁼ (Уь Уъ —, У_т} — вектор, элементами которого являются размеры штрафа за единицу невязки по /-му ресурсу; р_г — вероятность /--го исхода (г = 1, 2,..., Л); С= {с_и с₂,.,., с„] — вектор коэффициентов целевой функции; блок Ах = В₀ предназ­начен для отображения всех условий, не зависящих от случайностей.

2. Если случайной является матрица А технико-экономичес­ких коэффициентов ау, обозначающих размеры затрат ресурсов и выход продукции на единицу./-го вида деятельности, а вектор В детерминированный, то соответствующая задача линейного про­граммирования также имеет блочную структуру:

Аох = В₀

А\Х+ А^1 = В\ }

А₂х + Б₂у₂ = В₂

А_мх+ 0мун= В_м

х> 0, у, > 0, ..., ук> 0

Дх, У) = СХ + ряу_{ +р₂т +...+Р№м,

где х = [х_ь х_ъ..., х_п) — вектор управляющих переменных первого этапа; у_г= {у_1п у_2п •••> Утг) — вектор управляющих переменных второго этапа, соответствующих г-му исходу (г=1, 2,.,., Л⁷); А\, А₂,..., Ац— матрицы {тп) технико-экономических коэф­фициентов, соответствующие возможным исходам; О_ь Л,..., ^—вспомогатель­ные матрицы технико-экономических коэффициентов, необходимые для отобра­жения связи управляющих переменных г-го исхода с управляющими переменными первого этапа; В = {й_ь Ь₂,..., Ь_т] — вектор неизменяющихся свободных членов ог­раничений; С= {с,, с₂,..., с„} — вектор коэффициентов целевой функции при пере­менных первого этапа; у = {у_ь у₂,..., у} — вектор коэффициентов целевой функции при переменных второго этапа; д. — вероятность г-го исхода (г=\, 2,..., IV).

Блок Л(> х: =5₀ предназначен для отображения всех условий, не зависящих от случайностей.

Второй случай имеет большое значение для тех стохастичес­ких землеустроительных моделей, технико-экономические ко­эффициенты которых связаны с урожайностью сельскохозяй­ственных культур, обусловливающей случайный характер мат­рицы А. К этим моделям относятся задачи оптимизации транс­формации земель, определения оптимального сочетания отраслей и структуры земельных угодий, соотношения орошае­мых и богарных земель и т. д. Элементы вектора В в таких зада­чах могут рассматриваться в большинстве случаев как детерми­нированные величины (площади сельскохозяйственных угодий, трудовые ресурсы, планы производства и реализации продук­ции). Эти элементы не зависят от конкретных результатов года по урожайности.

Если случайный характер имеют одновременно параметры матрицы А и вектора В, то задачу линейного программирования можно построить путем комбинирования описанных выше при­емов.

В агроэкономических исследованиях рекомендуется исполь­зовать определенные критерии оптимальности для решения за­дач стохастического программирования. Эти же критерии могут применяться и для поиска оптимальных планов в землеустрои­тельных задачах. В качестве основных целевых функций (крите­риев) могут быть использованы следующие.

1. Максимум или минимум математического ожидания эф­
фекта:

р(х) = М{Сх) -> тах (тт),

где М— символ математического ожидания.

При этом дисперсия эффекта не учитывается. Данный крите­рий соответствует задачам, в которых критерием оптимальности является максимум стоимости валовой и товарной продукции, максимум прибыли и т. д. В стохастических задачах показателями качества решения будут соответственно математические ожида­ния названных величин. Этот критерий является наиболее рас­пространенным.

2. Минимум дисперсии эффекта:

ДСх)=1>

г „ л ЕС/*/

-> тт.

Задача сводится к выбору такого плана, при котором дис­персия эффекта будет минимальной. Для многих землеустро-

ительных задач уменьшение колеблемости результативного показателя весьма важно. Например, желательно выбирать та­кой план кормопроизводства, при котором колеблемость (дис­персия) объема производимых кормов является минимальной. При использовании этого критерия оптимальности устанавли­вают некоторое пороговое значение математического ожида­ния эффекта т₀, условие достижения которого вводится в мо­дель в качестве ограничения. В этом случае требуется опреде­лить

1шп ДСх) при М(Сх) > т₀.

Пороговое значение устанавливается на основе соответствую­щих нормативов, плановых заданий и т. д.

3. Линейная комбинация математического ожидания и дис­
персии линейной формы:

Сх-АхДх-> тах,

где Л — штраф за единицу дисперсии; й — квадратичная матрица, элементами ко­торой являются дисперсия и ковариация, например выходов продукции с 1 га по культурам; Зс —транспонированный вектор х переменных задач.

При использовании данного критерия трудно объективно оценить влияние дисперсии на выбор плана, то есть определить размер штрафа за дисперсию.

4. Максимальная вероятность превышения некоторого фик­
сированного значения эффекта:

Р(Сх> К) -» тах,

где К— заданное пороговое значение эффекта, превышение которого желательно.

Примерами могут служить сведения к максимуму вероятности того, что прибыль будет не менее заданного значения К или объем произведенной продукции заданного вида будет не менее необходимой потребности.

Таким образом, из всего многообразия постановок задач сто­хастического программирования необходимо выбрать ту, которая в наибольшей степени соответствует характеру и цели исследова­ния.