![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Lt;г,4/>0.
Со второй группой неравенств поступаем аналогично. Переносим р] вправо и делим на д7- < 0; при этом смысл неравенства меняется на противоположный. Получаем Чтобы удовлетворялось каждое неравенство второй группы, / надо определять по наименьшему из найденных значений: /< Ш1П ' РЛ Ч) Lt; 0. Объединяя оба результата в один, имеем
тах V Л Ъ) Gt; 0 Г Е?
д^< 0
Таким образом, для положительных коэффициентов д, пара-
метр ( должен быть больше наибольшего отношения Ч) отрицательных — меньше наименьшего. Если все коэффициенты < 7у одного знака, то вторым концом интервала изменения параметра является бесконечность соответствующего знака. Если < 7у = 0, то из условия следует, что в данном столбце р^> 0 и ц + д/=Р; +0-(= Р]> 0 для любого {. Поэтому такой столбец можно не принимать во внимание. Отыскав правую границу а! изменения параметра (левой границей на первом этапе всегда служит значение а), сравниваем интервал [а, а^ с заданным интервалом [а, Р]. Если первый из них больше, то задача решена: на всем отрезке [а, (3] найденное решение оптимально. Если же интервал [а, 0ц] меньше заданного, то исключаем его из рассмотрения, а для оставшегося отрезка [аь (3] задачу решаем заново. Так этап за этапом будут найдены все оптимальные планы. Рассмотрим пример (решение и исходные данные И. Ф. Полунина). Необходимо решить задачу параметрического программирования для целевой функции 2ГГ = (6 — 1)Х[ + (3 — 2{)х2 + /х3 -» тах, в которой / изменяется на отрезке [1; 3, 5], и ограничений XI + 2х2 + хз< 3; 2х[ — х2 + Зх3 < 7; х, -> 0, У= 1, 2, 3. Полагаем 1= 1 и получаем целевую функцию с постоянными коэффициентами 2, — 5х\ + х2 + хз -> тах. Составляем исходную жорданову таблицу, в которую заносим все нужные величины с учетом того, что верхним переменным Ху приписан знак «минус» (табл. 132). 132. Исходная таблица
План Х\ — х2 = х3 = 0 опорный, но не оптимальный. Выбираем в первом столбце разрешающий элемент и делаем шаг модифицированных жордановых исключений, преобразуя по общим правилам все элементы таблицы. Получаем таблицу 133, в 1{- строке которой стоят только положительные числа. Следовательно, для /= 1 план X! = 3, х2 = х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, х2 - 0, х3 = 1 оптимален. Найдем для него возможные значения параметра /. В последней строке таблицы 135 имеются как положительные, так и отрицательные коэффициенты ^. Для положительного коэффициента 2 по формуле тах V Р? <? у > *, Я]> 0 имеем -6 — тг-(г или 3 < /. Для отрицательных коэффициентов согласно формуле
/< 1ШП , #, < 0, находим ^тт[-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 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,..., х„). Оно не поддается корректировке при уточнении производственной ситуации. Например, априорным (предварительным) может быть решение, которое получают при усредненных значениях случайных параметров. Двухэтапные задачи основаны на применении двух последовательно получаемых решений. На первом этапе определяется априорное (предварительное) решение, которое уточняется на втором этапе в зависимости от изменения параметров случайных условий производства (исходов). Решение, получаемое на втором этапе, называется апостериорным. В моделях эти решения имеют вид стохастического вектора уг = (у\г, У2г, Укг)> применяемого с вероятностью рп где г— номер исходов (реализации случайных условий, г= 1, 2,..., Л). Термин «двухэтапная задача» имеет условный характер, так как разделение на этапы относится лишь к ее постановке. С точки зрения математического программирования это единственная задача, включающая одновременно переменные двух этапов, объединенные единой целевой функцией и системой ограничений. В настоящее время выделяют следующие постановки одно-этапных задач стохастического программирования. 1. Примитивная постановка задачи заключается в определении оптимального плана на основе решения обычной детерминированной задачи линейного программирования, коэффициенты которой рассчитаны путем усреднения случайных параметров и считаются условно детерминированными. Если случайным является только вектор (О-коэффициентов целевой функции, то для решения задачи достаточно заменить коэффициенты с, - их средними значениями су. Тогда целевая функция задачи примет вид Р(х)=М{Сх)= М(Сх)-> тах, где М— символ математического ожидания эффекта. 2. Жесткая постановка задачи требует, чтобы при любых конкретных реализациях (исходах) случайных параметров выполнялись все ограничения, то есть Агх < Д.для всех ге Я; х> 0; Р{х)=Сх-^тзх, где г — индекс возможной реализации (исхода) случайных параметров задачи; К — множество значений г, С — вектор средних значений целевой функции. Таким образом, решение одноэтапной стохастической задачи сводится к решению громоздкой детерминированной задачи линейного программирования при условиях: А{х< Ву А2х< В2 Арс< Вг А^х < 5дг х> 0 и целевой функции Р(х)=Сх-> тах, где г — номер возможной комбинации значений А и В, появляющихся с некоторой вероятностью (г= 1, 2,..., Л^. Исходя из этого следует, что решение данной задачи в стохастической постановке может быть сведено к задаче линейного программирования с «пессимистическими» значениями, то есть наихудшими величинами параметров технико- экономических коэффициентов и объемов ограничений. Жесткая постановка должна применяться тогда, когда нужно исключить риск. Этого требуют ситуации, когда выполнение хотя бы одного из ограничений задачи приводит к катастрофическим последствиям (например, к разорению и ликвидации сельскохозяйственного предприятия). 3. Вероятностная постановка задачи (с вероятностными ограничениями) — вероятность выполнения /-го ограничения должна быть не менее заданной величины й}'', то есть: Г0
> А(/\0< А(/)< 1, /=1, 2...... /я. Задача с вероятностными ограничениями обычно решается для ситуаций, когда случайным является вектор В, а матрица А и вектор С — детерминированы. Эта задача может быть также сведена к детерминированной задаче линейного программирования следующего вида:. Р(х)=Сх-^тах, Ах< В, х> 0. Элемент случайного вектора В=Ь^1=1, 2,..., т) вычисляют по уравнению вида Ь; где ф/(6,) — плотность распределения случайной величины Ь1. Если Р^-\, данная постановка переходит в жесткую. Методы постановки двухэтапных задач стохастического программирования делятся на непрямые и прямые. Непрямыми методами стараются свести зависимость Р(х, со), где со —вероятностный элемент, к зависимости Р(х), а затем применить один из известных методов математического программирования. Иными словами, стохастическую задачу сводят к ее детерминированному аналогу, а последний решают известными методами линейного или нелинейного программирования. К прямым методам относят методы, основанные на информации только о функции Р(х, со): методы стохастической аппроксимации, проектирования стохастических квазиградиентов и др. (Ермольев Ю. М. Стохастические модели и методы оптимизаций. — Киев: Кибернетика, 1974. — № 4). Рассмотрим рекомендуемые непрямые приемы сведения двухэтапных стохастических задач к задачам линейного программирования (Копенкин Ю. И. Стохастические задачи математического программирования. — В кн.: Математическое моделирование экономических процессов в сельском хозяйстве/ Под ред. А. М. Гатаулина. — М.: Агропромиздат, 1990. — С. 388—389). 1. Если случайным является вектор В (свободные члены ограничений Ьь обозначающие наличие ресурсов), а матрица А детерминированная, то двухэтапная стохастическая постановка допускает возникновение невязок в ограничениях (нехватку ресурсов) при отдельных исходах, однако им соответствует определенный штраф, который вычитается из целевой функции. Задача линейного программирования при этом имеет вид Ах -В^ Ах +Ду1 =51 Ах +ДУ2 =^2 Ах +Оух=Вх х> 0, У1> 0,..., ум> 0 Р{х, у) = Сх + р1уу1 + р2уу2 +... + рмуум, где х = {х\, х2,..., х„) — вектор основных переменных (управляющих переменных первого этапа); уг = {уХп у2г,..., утг] — вектор вспомогательных переменных (управляющих переменных второго этапа), обозначающих невязки в /-м ограничении при г-м исходе (/- = 1, 2,..., ЛО; Вг = {Ь1п Ь2п..., Ьтг) — вектор свободных членов ограничений, обозначающих наличие /-го ресурса при г-м исходе (г = 1, 2,..., ЛО; А — матрица размерностью тп неизменяющихся технико-экономических коэффициентов ау, обозначающих затраты /-го ресурса за единицу у-го вида деятельности; О — вспомогательная матрица, элементы которой служат для ввода в ограничения невязок (например, диагональная матрица, элементы главной диагонали которой равны —1); У = (Уь Уъ —, Ут} — вектор, элементами которого являются размеры штрафа за единицу невязки по /-му ресурсу; рг — вероятность /--го исхода (г = 1, 2,..., Л); С= {си с2,.,., с„] — вектор коэффициентов целевой функции; блок Ах = В0 предназначен для отображения всех условий, не зависящих от случайностей. 2. Если случайной является матрица А технико-экономических коэффициентов ау, обозначающих размеры затрат ресурсов и выход продукции на единицу./-го вида деятельности, а вектор В детерминированный, то соответствующая задача линейного программирования также имеет блочную структуру: Аох = В0 А\Х+ А^1 = В\ } А2х + Б2у2 = В2 Амх+ 0мун= Вм х> 0, у, > 0, ..., ук> 0 Дх, У) = СХ + ряу{ +р2т +...+Р№м, где х = [хь хъ..., хп) — вектор управляющих переменных первого этапа; уг= {у1п у2п •••> Утг) — вектор управляющих переменных второго этапа, соответствующих г-му исходу (г=1, 2,.,., Л7); А\, А2,..., Ац— матрицы {тп) технико-экономических коэффициентов, соответствующие возможным исходам; Оь Л,..., ^—вспомогательные матрицы технико-экономических коэффициентов, необходимые для отображения связи управляющих переменных г-го исхода с управляющими переменными первого этапа; В = {йь Ь2,..., Ьт] — вектор неизменяющихся свободных членов ограничений; С= {с,, с2,..., с„} — вектор коэффициентов целевой функции при переменных первого этапа; у = {уь у2,..., у} — вектор коэффициентов целевой функции при переменных второго этапа; д. — вероятность г-го исхода (г=\, 2,..., IV). Блок Л(> х: =50 предназначен для отображения всех условий, не зависящих от случайностей. Второй случай имеет большое значение для тех стохастических землеустроительных моделей, технико-экономические коэффициенты которых связаны с урожайностью сельскохозяйственных культур, обусловливающей случайный характер матрицы А. К этим моделям относятся задачи оптимизации трансформации земель, определения оптимального сочетания отраслей и структуры земельных угодий, соотношения орошаемых и богарных земель и т. д. Элементы вектора В в таких задачах могут рассматриваться в большинстве случаев как детерминированные величины (площади сельскохозяйственных угодий, трудовые ресурсы, планы производства и реализации продукции). Эти элементы не зависят от конкретных результатов года по урожайности. Если случайный характер имеют одновременно параметры матрицы А и вектора В, то задачу линейного программирования можно построить путем комбинирования описанных выше приемов. В агроэкономических исследованиях рекомендуется использовать определенные критерии оптимальности для решения задач стохастического программирования. Эти же критерии могут применяться и для поиска оптимальных планов в землеустроительных задачах. В качестве основных целевых функций (критериев) могут быть использованы следующие. 1. Максимум или минимум математического ожидания эф р(х) = М{Сх) -> тах (тт), где М— символ математического ожидания. При этом дисперсия эффекта не учитывается. Данный критерий соответствует задачам, в которых критерием оптимальности является максимум стоимости валовой и товарной продукции, максимум прибыли и т. д. В стохастических задачах показателями качества решения будут соответственно математические ожидания названных величин. Этот критерий является наиболее распространенным. 2. Минимум дисперсии эффекта: ДСх)=1> г „ л ЕС/*/ -> тт. Задача сводится к выбору такого плана, при котором дисперсия эффекта будет минимальной. Для многих землеустро- ительных задач уменьшение колеблемости результативного показателя весьма важно. Например, желательно выбирать такой план кормопроизводства, при котором колеблемость (дисперсия) объема производимых кормов является минимальной. При использовании этого критерия оптимальности устанавливают некоторое пороговое значение математического ожидания эффекта т0, условие достижения которого вводится в модель в качестве ограничения. В этом случае требуется определить 1шп ДСх) при М(Сх) > т0. Пороговое значение устанавливается на основе соответствующих нормативов, плановых заданий и т. д. 3. Линейная комбинация математического ожидания и дис Сх-АхДх-> тах, где Л — штраф за единицу дисперсии; й — квадратичная матрица, элементами которой являются дисперсия и ковариация, например выходов продукции с 1 га по культурам; Зс —транспонированный вектор х переменных задач. При использовании данного критерия трудно объективно оценить влияние дисперсии на выбор плана, то есть определить размер штрафа за дисперсию. 4. Максимальная вероятность превышения некоторого фик Р(Сх> К) -» тах, где К— заданное пороговое значение эффекта, превышение которого желательно. Примерами могут служить сведения к максимуму вероятности того, что прибыль будет не менее заданного значения К или объем произведенной продукции заданного вида будет не менее необходимой потребности. Таким образом, из всего многообразия постановок задач стохастического программирования необходимо выбрать ту, которая в наибольшей степени соответствует характеру и цели исследования.
|