Математика (3 сем-р) (стр. 2 )

II этап. Найти угловую точку, в которой целевая функция принимает оптимальное значение.

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

Выберем произвольное значение целевой функции F=F0. Получим уравнение прямой F0=c1x1+c2x2 в системе координат . Эту прямую также называют линией уровня целевой функции, то есть линией постоянного значения. Положим F0=0, получаем линию уровня, проходящую через начало координат. При F>F0 линия уровня будет лежать параллельно первоначальной дальше от начала координат в направлении вектора . Очевидно, что все линии уровня параллельны между собой и, соответственно, перпендикулярны векторам – планам задачи.

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

III этап. Найти координаты оптимальной угловой точки (это будет оптимальный план) и оптимальное значение целевой функции.

Пример 1. Решить графически:

Теперь рассмотрим другие частные случаи ОДР на плоскости.

1.  ОДР представляет собой неограниченную в направлении вектора роста целевой функции многоугольную область. В этом случае оптимального решения не существует, целевая функция стремится к бесконечности.

2.  ОДР состоит из единственной точки. Этот случай встречается крайне редко, и тогда задача имеет единственное допустимое решение, которое является одновременно оптимальным

3. ОДР – пустое множество. В этом случае система ограничений задачи противоречива, и задача вообще не имеет допустимых, а, следовательно, и оптимальных решений.

4. Задача имеет бесконечное множество оптимальных решений. Это происходит, когда две угловые точки ОДР являются оптимальными; следовательно, оптимальными являются и все точки, лежащие на участке границы между этими угловыми точками.

Замечание. Графическим методом можно решить ЗЛП и с большим числом неизвестных, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением: так как в этом случае методом исключения Жордана – Гаусса можно перейти к двум переменным. Решая эту задачу графически, находят две компоненты оптимального плана. Подставляя их в ограничения задачи, определяют и остальные компоненты.

4.2. Симплексный метод линейного программирования

Это универсальный метод решения ЗЛП.

Рассмотрим ЗЛП в стандартной форме:

.

Алгоритм симплексного метода:

1. Приводим ЗЛП к канонической форме.

Для этого в каждое неравенство системы ограничений вводим дополнительные неотрицательные переменные , и систему ограничений записываем в виде т. н. расширенной системы:

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

2. Находим первоначальное базисное решение (опорный план).

Для этого разбиваем все переменные на две группы: базисные (основные) и свободные (неосновные). Базисные переменные – это любые m переменных, определитель из коэффициентов при которых в системе нетривиальных ограничений не равен нулю. Остальные переменные в этой системе являются свободными. Естественно, выбор базиса в такой системе не является единственным. Как правило, в качестве базиса на первом шаге выбирают дополнительные переменные (т. к. определитель из коэффициентов при них не равен 0), а переменные - являются свободными.

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

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

3. Составим первую симплексную таблицу:

Базис	Своб. члены		…			…		Оценоч. отношен
			…		1	…	0
…	…	…	…	…	…	…	…
			…		0	…	1
F			…		0	…	0

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

Второй столбец состоит из свободных членов расширенной системы.

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

Последний столбец служит для оценочных отношений (ограничений на базисные переменные), которые рассмотрим позже.

Остальная часть таблицы состоит из коэффициентов при переменных в уравнениях расширенной системы.

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

Если критерий оптимальности не выполнен, то полученный план можно улучшить. Переход к новому, лучшему опорному плану называется итерацией симплекс-метода. Она представляет собой преобразование однократного замещения, поскольку при этом происходит переход к новому базису: одна из базисных переменных становится свободной, а в базис, наоборот, входит одна из бывших свободных переменных.

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

Теперь определим переменную, “покидающую” базис. Это делается с помощью оценочных (симплексных) отношений, обозначенных в последнем столбце симплекс-таблицы, которые находим для каждой строки по правилам:

А) отношение равно ∞, если свободный член и коэффициент из ведущего столбца имеют разные знаки;

Б) ∞, если = 0;

В) ∞, если = 0, < 0;

Г) 0, если = 0, > 0;

Д) , если и имеют одинаковые знаки.

Выбираем минимальное из найденных отношений. Если конечного минимума нет, то задача не имеет конечного оптимума (Fmax = ∞). Если минимум конечен, то выбираем строку q, на которой он достигается. Эта строка называется ведущей строкой. В той же строке находится переменная , покидающий наш первоначальный базис. На пересечении ведущих строки и столбца находится ведущий элемент .

6. Переходим к новой таблице по правилам:

А) в первом столбце записываем новый базис: переменную заменяем на переменную , остальные переменные переписываем без изменений;

Б) в базисных столбцах проставляем нули и единицы: единицу напротив «своей» базисной переменной, остальные нули;

В) новую строку с номером q получаем из старой делением на ведущий элемент;

Г) остальные элементы вычисляем по правилу прямоугольника:

Для любого элемента первоначальной таблицы можно определить прямоугольник

 

 

Здесь – ведущий элемент, – искомый элемент, , – элементы, находящиеся с ними на пересечении строк и столбцов.

Новое значение элемента получается из формулы: – это и есть правило прямоугольника.

Переходим к п.4 алгоритма.

Пример 1 решить симплекс-методом:

Тема 2 Теория двойственности в линейном программировании

Каждой ЗЛП соответствует другая задача, которая называется двойственной или сопряженной по отношению к исходной. Теория двойственности полезна для проведения качественных исследований ЗЛП.

В.1. Экономическая интерпретация задачи, двойственной

задаче о планировании производства

Рассмотрим прямую задачу планирования производства (об использовании ресурсов): найти план , который обеспечивает максимум целевой функции

(1)

при ограничениях

(2)

(3)

Пусть теперь на предприятии решили рассмотреть другой вариант извлечения прибыли не через производство и продажу готовых изделий, а путем продажи имеющихся запасов сырья. Возникает новая задача, называемая двойственной: какова должна быть цена единицы каждого из ресурсов , чтобы эта продажа имела смысл? Таким образом, нужно найти вектор цен .

Целью покупателя является минимизация затрат на приобретение ресурсов в количествах по цене :

(4)

Цель продавца: выручка за сырьё, идущее на производство единицы продукции каждого вида, должна быть не меньше цены единицы этой продукции (иначе выгоднее самому организовать производство).

Рассмотрим себестоимость единицы продукции первого вида в этих учетных ценах. Стоимость ресурса первого вида в этой продукции равна , стоимость ресурса второго вида равна , и т. д., стоимость m-го ресурса в первом изделии составляет . Просуммируем эти величины, получим себестоимость первого изделия, которая должна быть не меньше цены реализации этого изделия С1.. Аналогичные неравенства составим и для всех остальных видов продукции, получаем ограничения двойственной задачи:

(5)

Ограничения на переменные традиционны (поскольку цены на ресурсы не могут быть отрицательными):

(6)

Итак, задача (4)-(6) – двойственная к задаче (1)-(3): Найти такой набор цен ресурсов , при котором общие затраты на ресурсы будут минимальными.

Цены называются учетными (неявными, теневыми). Т. к. это ненастоящие цены. В отличие от «внешних» цен на продукцию, известных до производства цены ресурсов являются «внутренними» и определяются в процессе производства. Их называют оценками ресурсов.

Получили пару симметричных двойственных задач.

В.2. Взаимно двойственные ЗЛП и их свойства

Рассмотрим формально задачи.

Две задачи (1)-(3) и (4)-(6) линейного программирования называются симметричными взаимно двойственными (двойственными) задачами, если они обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой – минимум.

2.Каждая из задач задана в стандартной форме, причем в задаче на максимум все неравенства вида «≤», в задаче на минимум – «≥».

3.Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

4.Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений другой.

5.Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.

6.Условия неотрицательности имеются в обеих задачах.

Из определения следует алгоритм составления двойственной задачи:

1.  Приводим все неравенства системы ограничений исходной задачи к одному виду: если задача максимизации «≤», минимизации – «≥». Для этого неравенства, в которых это требование не выполняется умножим на «-1».

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

3.  Транспонируем расширенную матрицу.

4.  Сформулируем двойственную задачу на основании транспонированной матрицы и условии неотрицательности переменных.

2-й алгоритм:

·  Матрица системы ограничений транспонируется.

·  Свободные члены исходной задачи становятся коэффициентами целевой функции задачи двойственной

·  Коэффициенты целевой функции исходной задачи становятся свободными членами двойственной.

·  Ограничения вида «меньше или равно» заменяются на «больше или равно».

·  Исходная задача на максимум преобразуется в двойственную к ней на минимум.

Пример 1. Составить двойственную задачу к задаче:

В.3. Исследование пары двойственных задач. Определение двойственных оценок ЗЛП

Поскольку двойственная задача также является ЗЛП, то её можно решить симплекс-методом. Однако двойственная задача и экономически, и математически тесно связана с прямой задачей, поэтому есть более простые способы её решения, если известно решение прямой задачи. Поэтому рассмотрим некоторые результаты, связывающие обе эти задачи.

Теорема. Пусть есть допустимое решение задачи (1)-(3), есть допустимое решение задачи (4)-(6). Тогда выполняется неравенство:

(7)

Теорема (достаточный признак оптимальности пары двойственных ЗЛП, или критерий оптимальности Канторовича). Если - такие допустимые решения (1)-(3) и (4)-(6) соответственно, что , то являются оптимальными решениями своих задач.

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

(8)

Если же линейная функция одной из задач неограниченна (), то условия другой задачи противоречивы.

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

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

(9)

(10)

Формулы (9) и (10) можно применять следующим образом:

- если при оптимальном решении одной из пары двойственных задач какое-либо неравенство выполняется как строгое, то соответствующая ему двойственная переменная в оптимальном решении другой задачи равна нулю;

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

Пример 2. Рассмотрим пример 1 задачи об использовании ресурсов, тема «ЗЛП»:

Составить двойственную задачу и найти ее решение.

Решение. Эта задача в двойственной форме имеет вид:

Исходная задача была нами решена графически, и решение равно , .

Найдем решение двойственной задачи. Согласно первой теореме двойственности . Для того, чтобы найти оптимальный план двойственной задачи воспользуемся 2-й теоремой двойственности и подставим компоненты плана в ограничения исходной задачи. В результате видно, что первое и второе ограничения выполняются как точные равенства, а третье и четвертое ограничения являются строгими неравенствами. Согласно теореме, третья и четвертая переменная двойственной задачи должны быть равны нулю, т. е. . Согласно этой же теореме, поскольку обе компоненты решения исходной задачи не равны нулю, оба ограничения двойственной задачи выполняются как равенства. Если в этих равенствах обнулить , то получим систему двух уравнений с двумя неизвестными:

Решая эту систему, получаем решение двойственной задачи .

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