Министерство образования РФ и РТ.
Казанский Государственный Университет им. А.Н. Туполева.
_______________________________________________Курсовая работа по дисциплине
«Численные методы оптимизации»Решение задач линейной оптимизации симплекс – методом.
Выполнил: ст.гр.4408 Калинкин
А.А.Проверил: Мурга О.К.
г. Казань 2001г.
Содержание| |
|1. Постановка задачи |
| |
|1.1. Физическая постановка задачи |
|1.2. Математическая постановка задачи |
| |
|2. Приведение задачи к канонической форме |
| |
|3. Нахождение начального опорного плана с помощью L-задачи |
| |
|3.1. Постановка L-задачи |
|3.2. Решение L-задачи |
|3.3. Формирование начального опорного плана исходной задачи линейного |
|программирования из оптимального плана L-задачи |
| |
|4. Решение исходной задачи I алгоритмом симплекс-метода |
| |
|5. Формирование М-задачи |
| |
|6. Решение М-задачи вторым алгоритмом симплекс-метода |
| |
|7. Формирование двойственной задачи |
| |
|8. Формирование оптимального решения двойственной задачи на основе теоремы |
|о двойственности |
| |
|9. Анализ результатов и выводы |1. Постановка задачи
1.1. Физическая (техническая) постановка задачи
Нефтеперерабатывающий завод получает четыре полуфабриката:
— 400 тыс. л. алкилата;
— 250 тыс. л. крекинг-бензина;
— 350 тыс. л. бензина прямой перегонки;
— 250 тыс. л. изопентона;
В результате смешивания этих четырёх компонентов в разных пропорциях
образуются три сорта авиационного бензина:
— Бензин А – 2 : 3 : 5 : 2 ;
— Бензин В – 3 : 1 : 2 : 1 ;
— Бензин С – 2 : 2 : 1 : 3 ;
Стоимость 1 тыс.л. указанных сортов бензина:
— Бензин А – 120 руб.
— Бензин Б – 100 руб.
— Бензин С – 150 руб.
Необходимо определить план смешения компонентов, при котором будет
достигнута максимальная стоимость все продукции. При следующих условиях:
— Бензина каждого сорта должно быть произведено не менее 300 тыс..л.
— Неиспользованного крекинг бензина должно остаться не более 50 тыс.л.Сводная таблица условий задачи:
| |Сорта |Объем |
|Компоненты, используемые для |производимого |ресурсов|
|производства трёх видов |бензина | |
|бензина. | |(тыс. л)|
| |А |В |С | |
|Алкилат |[pic|[pic|[pic|400 |
| |] |] |] | |
|Крекинг-бензин |[pic|[pic|[pic|250 |
| |] |] |] | |
|Бензин прямой перегонки |[pic|[pic|[pic|300 |
| |] |] |] | |
|Изопентат |[pic|[pic|[pic|250 |
| |] |] |] | |
|Цена бензина (рублей за 1 |120 |100 |150 | |
|тыс.л.) | | | | |1.2. Математическая постановка задачи
Исходя из условий задачи, необходимо максимизировать следующую целевую
функцию:[pic] (1.2.1)
при ограничениях
[pic] (1.2.2)
[pic], где [pic]
В этих выражениях:
[pic] — объемы бензина А-го, В-го и С-го сорта соответственно.
Тогда
[pic]объёмная доля первой компоненты (алкилата) в бензине А.
[pic]объёмная доля первой компоненты (алкилата) в бензине В.
[pic]объёмная доля первой компоненты (алкилата) в бензине С.
и т.д.
Целевая функция [pic] выражает стоимость всей продукции в зависимости от
объема производимого бензина каждого сорта. Таким образом, для получения
максимальной стоимости продукции необходимо максимизировать целевую функцию
[pic] (1.2.1) с соблюдением всех условий задачи, которые накладывают
ограничения (1.2.2) на [pic].2. Приведение задачи к канонической форме
Задача линейного программирования записана в канонической форме, если
она формулируется следующим образом.
Требуется найти вектор [pic], доставляющий максимум линейной форме
[pic] (2.1)
при условиях
[pic] (2.2)
[pic] (2.3)
где [pic]Перепишем исходную задачу (1.2.1) — (1.2.2):
[pic] (2.4)
при ограничениях
[pic] (2.5)
[pic], где [pic]
(2.6)
В канонической форме задачи линейного программирования необходимо,
чтобы все компоненты искомого вектора Х были неотрицательными, а все
остальные ограничения записывались в виде уравнений. Т.е. в задаче
обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида
(2.2), обусловленных неравенствами (2.5), (2.6).
Число ограничений задачи, приводящих к уравнениям (2.2) можно
уменьшить, если перед приведением исходной задачи (2.4) — (2.6) к
канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого
перенесем свободные члены правых частей неравенств (2.6) в левые части.
Таким образом, от старых переменных [pic] перейдем к новым переменным[pic],
где [pic]:
[pic], [pic].
Выразим теперь старые переменные через новые
[pic], [pic] (2.7)
и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим[pic]
[pic]
[pic], где [pic].
Раскрывая скобки и учитывая, что
[pic] (2.8),
можем окончательно записать:[pic] (2.9)
[pic] (2.10)
[pic], где [pic]
(2.11)Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче
(2.9) — (2.11) с меньшим числом ограничений.Для записи неравенств (2.10) в виде уравнений введем неотрицательные
дополнительные переменные [pic], и задача (2.9) — (2.11) запишется в
следующей эквивалентной форме:[pic] (2.12)
[pic] (2.13)
[pic], где [pic]Задача (2.12), (2.13) имеет каноническую форму.
3. Нахождение начального опорного плана с помощью L-задачи
Начальный опорный план задачи (2.1) — (2.3), записанной в канонической
форме, достаточно легко может быть найден с помощью вспомогательной задачи
(L-задачи):[pic] (3.1)
[pic] (3.2)
[pic] (3.3)Начальный опорный план задачи (3.1) — (3.3) известен. Он состоит из
компонент[pic]
и имеет единичный базис Б = [pic]= E.
Решая вспомогательную задачу первым алгоритмом симплекс-метода
(описание алгоритма приводится в п.4), в силу ограниченности линейной формы
[pic]сверху на множестве своих планов ([pic]) получим, что процесс решения
через конечное число шагов приведет к оптимальному опорному плану
вспомогательной задачи.
Пусть [pic]- оптимальный опорный план вспомогательной задачи. Тогда
[pic] является опорным планом исходной задачи. Действительно, все
дополнительные переменные [pic]. Значит, [pic]удовлетворяет условиям
исходной задачи, т.е. является некоторым планом задачи (2.12) — (2.13). По
построению план [pic]является также опорным.3.1. Постановка L-задачи
Вспомогательная задача для нахождения начального опорного плана задачи
(2.12) — (2.13) в канонической форме состоит в следующем.
Требуется обратить в максимум
[pic]
при условиях
[pic]
[pic], где [pic].
рассматривая в качестве исходного опорного плана план
Здесь добавление только одной дополнительной переменной [pic] (вместо
пяти) обусловлено тем, что исходная задача уже содержит четыре единичных
вектора условий А4, А5, А6, А7.3.2. Решение L-задачи
Решение L-задачи будем проводить в соответствии с первым алгоритмом
симплекс-метода (описание алгоритма приводится в п.4). Составим таблицу,
соответствующую исходному опорному плану (0-й итерации).
Т.к. Б0 = [pic]- базис, соответствующий известному опорному плану[pic],
является единичной матрицей, то коэффициенты разложения векторов Аj по
базису Б0
[pic].
Значение линейной формы [pic] и оценки [pic] для заполнения (m+1)-й
строки таблицы определяются следующими соотношениями:
[pic],
[pic].
Отсюда получим:[pic];
[pic];
[pic];
…
[pic].Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из
2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям.
Заполняем таблицу 0-й итерации.
Среди оценок [pic] имеются отрицательные. Значит, исходный опорный план
не является оптимальным. Перейдем к новому базису. В базис будет введен
вектор А1 с наименьшей оценкой [pic]. Значения t вычисляются для всех
позиций столбца t (т.к. все элементы разрешающего столбца положительны).
Наименьший элемент [pic] достигается на пятой позиции базиса. Значит, пятая
строка является разрешающей строкой, и вектор А9 подлежит исключению из
базиса.
Составим таблицу, отвечающую первой итерации.
В столбце Бх, в пятой позиции базиса место вектора А9 занимает вектор
А1. Соответствующий ему коэффициент линейной формы С41 = 0 помещаем в
столбец Сх. Главная часть таблицы 1 заполняется по данным таблицы 0 в
соответствии с рекуррентными формулами. Так как все [pic], то опорный план
[pic] является решением L-задачи. Наибольшее значение линейной формы равно
[pic].Таблица 3.2.1
[pic]
3.3. Формирование начального опорного плана исходной задачи линейного
программирования из оптимального плана L-задачиПоскольку [pic], где [pic] [pic]- оптимальный опорный план L-задачи,
то [pic] [pic]является начальным опорным планом исходной задачи (2.12) —
(2.13).4. Решение исходной задачи I алгоритмом симплекс-метода
Описание I алгоритма
Симплекс-метод позволяет, отправляясь от некоторого исходного опорного
плана и постепенно улучшая его, получить через конечное число итераций
оптимальный план или убедиться в неразрешимости задачи. Каждой итерации
соответствует переход от одной таблицы алгоритма к следующей. Таблица,
отвечающая опорному плану в ?-й итерации имеет вид табл. 4.1.Таблица 4.1
| | | |C |[pi|… |[pi|… |[pi|… |[pi| |
| | | | |c] | |c] | |c] | |c] | |
|N |[pi|[pi|B |[pi|… |[pi|… |[pi|… |[pi|t |
| |c] |c] | |c] | |c] | |c] | |c] | |
|1 |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi| |
| |c] |c] |c] |c] | |c] | |c] | |c] | |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |
|] |c] |c] |c] |c] |c] |c] |c] |c] |c] |c] | |
|l |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi|[pi|
| |c] |c] |c] |c] | |c] | |c] | |c] |c] |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |
|] |c] |c] |c] |c] |c] |c] |c] |c] |c] |c] | |
|m |[pi|[pi|[pi|[pi|… |[pi|… |[pi|… |[pi| |
| |c] |c] |c] |c] | |c] | |c] | |c] | |
|m+1 |– |– |[pi|[pi|… |[pi|… |[pi|… |[pi|– |
| | | |c] |c] | |c] | |c] | |c] | |Заполнение таблицы, соответствующей исходному опорному плану (0-й
итерации). Пусть [pic] некоторый опорный план задачи (2.1) — (2.3) с
базисом [pic]. Тогда [pic] – базисные компоненты, а [pic] – небазисные
компоненты.Вычисляем коэффициенты разложения векторов Аj по базису Б0
[pic] (в случае, если Б0 является единичной матрицей, [pic])
и находим оценки [pic]. Далее определяем значение линейной формы
[pic]
Полученные результаты записываем в таблицу 4.1.
В первом столбце N таблицы указываются номера строк. Номера первых m
строк совпадают с номерами позиций базиса. Во втором столбце Сх
записываются коэффициенты [pic]линейной формы при базисных переменных.
Столбец Бх содержит векторы базиса [pic]. В столбце В записываются базисные
переменные [pic] опорного плана. Столбцы [pic]содержат коэффициенты
[pic]разложения соответствующих векторов условий [pic] по векторам базиса.
Все вышесказанное относится только к первым m строкам таблицы. Последняя
(m+1)-я строка таблицы заполняется последовательно значением линейной формы
F и оценками [pic]. Позиции таблицы, которые не должны заполняться,
прочеркиваются.
В результате заполнена таблица 0-й итерации кроме столбца t.
Столбцы В, А1,…, An (все m+1 позиций) будем называть главной частью
таблицы.
Порядок вычислений в отдельной итерации. Пусть ?-я итерация закончена.
В результате заполнена таблица ? за исключением последнего столбца t.
Каждая итерация состоит из двух этапов.
I этап: проверка исследуемого опорного плана на оптимальность.
Просматривается (m+1)-я строка таблицы ?. Если все [pic], то опорный
план, полученный после ?-й итерации, является оптимальным (случай 1),
завершаем решение задачи. Пусть теперь имеются отрицательные оценки.
Проверяем знаки элементов [pic] столбцов [pic] с [pic]. Наличие по крайней
мере одного столбца [pic], для которого [pic] и все [pic], свидетельствует
о неразрешимости задачи (случай 2). Установив это, прекращаем вычисления.
Если в каждом столбце [pic], для которого [pic], содержится хотя бы
один положительный коэффициент [pic], то опорный план является
неоптимальным (случай 3). Переходим ко II этапу.
II этап: построение нового опорного плана с большим значением линейной
формы.
Определяется вектор Ak, который должен быть введен в базис, из
следующего условия
[pic].
После этого заполняется последний столбец таблицы ? – столбец t. В него
записываются отношения базисных переменных [pic] (элементы столбца В) к
соответствующим составляющим [pic] (элементы столбца Ak). Т.о. заполняются
только те позиции, для которых [pic]. Если [pic], то в позиции i столбца t
записывается [pic]. Вектор базиса [pic], на котором достигается t0,
[pic],
подлежит исключению из базиса (если t0 достигается на нескольких векторах,
то из базиса исключается любой из них).
Столбец Ak , отвечающий вектору, вводимому в базис, и l-я строка,
соответствующая вектору [pic], исключаемому из базиса, называется
соответственно разрешающим столбцом и разрешающей строкой. Элемент [pic],
расположенный на пересечении разрешающего столбца и разрешающей строки,
называется разрешающим элементом.
После выделения разрешающего элемента заполняется (?+1)-я таблица. В l-
е позиции столбцов Бх, Сх вносятся соответственно Ак, Ск, которые в (?+1)-й
таблице обозначаются как [pic], [pic]. В остальные позиции столбцов Бх, Сх
вносятся те же параметры, что и в таблице ?.
Далее заполняется главная часть (?+1)-й таблицы. Прежде всего
происходит заполнение ее l-й строки в соответствии с рекуррентной формулой
[pic].
Рекуррентная формула для заполнения i-й строки (?+1)-й таблицы имеет
вид
[pic].
Здесь
[pic].
Заполнение главной части (?+1)-й таблицы завершает (?+1)-ю итерацию.
Последующие итерации проводятся аналогично. Вычисления продолжаются до тех
пор, пока не будет получен оптимальный план либо будет установлено, что
исследуемая задача неразрешима.Решение исходной задачи
Весь процесс решения исходной задачи (2.12) — (2.13) приведен в
табл. 4.2.
Заполнение таблицы, отвечающей 0-й итерации, происходит на основе
табл. 3.2.1 (см. итерацию 1) следующим образом. Главная часть таблицы 0-й
итерации исходной задачи (за исключением (m+1)-й строки) полностью
повторяет главную часть таблицы заключительной итерации L-задачи без
столбца А9. Также без изменений остается столбец базисных векторов Бх.
Строка С коэффициентов линейной формы исходной задачи и столбец Сх
коэффициентов при базисных переменных заполняются исходя из (2.12). С
учетом новых коэффициентов С пересчитываются значение линейной формы F и
оценки [pic].
Заполнение таблиц, отвечающих последующим итерациям, происходит в
соответствии с описанным выше первым алгоритмом.Таблица 4.2
[pic]Решение исходной задачи (2.12) — (2.13) получено за 3 итерации.
Оптимальный план ее равен [pic] и [pic].
Найденное решение [pic] задачи в канонической форме (2.12) — (2.13)
соответствует решению [pic] (4.1) общей задачи линейного программирования
(2.9) — (2.11), записанной для новых переменных [pic]. Для общей задачи из
(2.9) следует, что [pic] (4.2).
Вернемся к задаче (1.2.1), (1.2.2) со старыми переменными [pic].
Учитывая (4.1) и (4.2) из (2.7) и (2.8) получим[pic] (4.3)
и
[pic]. (4.4)
Таким образом, для получения максимальной цены (142750 руб.) всей
продукции необходимо произвести:
— 450 тыс.л. бензина А из полуфабрикатов в следующих количествах:
— Алкитата [pic]тыс.л.
— Крекинг-бензина [pic]тыс.л.
— Бензина прямой перегонки [pic]тыс.л.
— Изопентона [pic]тыс.л.
— [pic] тыс.л. бензина В из полуфабрикатов в следующих количествах:
— Алкитата [pic]тыс.л.
— Крекинг-бензина [pic]тыс.л.
— Бензина прямой перегонки [pic]тыс.л.
— Изопентона [pic]тыс.л.
— 300 тыс.л. бензина В из полуфабрикатов в следующих количествах:
— Алкитата [pic]тыс.л.
— Крекинг-бензина [pic]тыс.л.
— Бензина прямой перегонки [pic]тыс.л.
— Изопентона [pic]тыс.л.5. Формирование М-задачи
Далеко не всегда имеет смысл разделять решение задачи линейного
программирования на два этапа – вычисление начального опорного плана и
определение оптимального плана. Вместо этого решается расширенная задача (М-
задача). Она имеет другие опорные планы (один из них всегда легко указать),
но те же решения (оптимальные планы), что и исходная задача.
Рассмотрим наряду с исходной задачей (2.1) — (2.3) в канонической форме
следующую расширенную задачу (М-задачу):[pic] (5.1)
[pic] (5.2)
[pic]. (5.3)
Здесь М>0 – достаточно большое число.Начальный опорный план задачи (5.1) — (5.3) имеет вид
[pic]
Переменные [pic] называются искусственными переменными.
Таким образом, исходная задача линейного программирования с неизвестным
заранее начальным опорным планом сводится к М-задаче, начальный опорный
план которой известен. В процессе решения этой расширенной задачи можно
либо вычислить оптимальный план задачи (2.1) — (2.3), либо убедиться в ее
неразрешимости, если оказывается неразрешимой М-задача.В соответствии с вышеизложенным имеем: требуется решить задачу
(2.12), (2.13), записанную в канонической форме. Введем искусственную
неотрицательную переменную х9 и рассмотрим расширенную М-задачу
[pic] (5.4)
при условиях
[pic] (5.5)
[pic], где [pic].
где М – сколь угодно большая положительная величина.Как и в L-задаче, добавление только одной искусственной переменной
[pic] (вместо пяти) обусловлено тем, что исходная задача уже содержит
четыре единичных вектора условий А4, А5, А6, А7.6. Решение М-задачи II алгоритмом симплекс-метода
Описание II алгоритма
Второй алгоритм (или метод обратной матрицы) симплекс метода основан на
ином способе вычисления оценок [pic] векторов условий Аj, чем в первом
алгоритме.
Рассматривается задача линейного программирования в канонической форме
(2.1) — (2.3). Пусть Х – опорный план с базисом [pic]. Все параметры,
необходимые для оценки плана на оптимальность и перехода к лучшему плану,
можно получить, преобразовывая от шага к шагу элементы матрицы [pic].Действительно, зная обратную матрицу [pic], можно получить базисные
составляющие опорного плана:[pic]
и вычислить оценки векторов условий относительно текущего базиса
[pic], (6.1)
предварительно определив вектор-строку [pic] по формуле
[pic]
или
[pic]. (6.2)
Здесь [pic]- вектор-строка из коэффициентов линейной формы, отвечающих
базисным переменным.
Оценки [pic] позволяют установить оптимальность рассматриваемого
опорного плана и определить вектор Ак, вводимый в базис. Коэффициенты [pic]
разложения вектора Ак по текущему базису вычисляются по формуле
[pic].
Как и в I алгоритме, вектор, подлежащий исключению из базиса,
определяется величиной
[pic].
Таким образом при втором алгоритме на каждом шаге запоминаются базисные
компоненты [pic], обратная матрица [pic], значение линейной формы F(X) и
вектор Y, соответствующие текущему опорному плану Х. Элементы столбцов
матрицы [pic] удобно рассматривать как коэффициенты [pic] разложения
единичных векторов [pic] по векторам базиса. Рекуррентные формулы,
связывающие параметры двух последовательных итераций
[pic]; (6.3)
[pic]. (6.3)
Здесь
[pic].Результаты вычислений сводятся в основные таблицы (вида табл. 6.1) и
вспомогательную таблицу (вида табл. 6.2); столбцы В, е1, …, еm основных
таблиц (все m+1 позиций) называют главной частью этих таблиц. Столбец Аk –
разрешающий столбец, строка l – разрешающая строка.Таблица 6.1 Таблица
6.2|N |[pi|[pi|B |[pi|… |[pi|[pi|t | |N |B |[pi|[pi|… |[pi|
| |c] |c] | |c] | |c] |c] | | | | |c] |c] | |c] |
|1 |[pi|[pi|[pi|[pi|… |[pi|[pi| | |1 |[pi|[pi|[pi|… |[pi|
| |c] |c] |c] |c] | |c] |c] | | | |c] |c] |c] | |c] |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |[pic|[pi|[pi|[pi|[pi|[pi|
|] |c] |c] |c] |c] |c] |c] |c] |c] | |] |c] |c] |c] |c] |c] |
|l |[pi|[pi|[pi|[pi|… |[pi|[pi|[pi| |m |[pi|[pi|[pi|… |[pi|
| |c] |c] |c] |c] | |c] |c] |c] | | |c] |c] |c] | |c] |
|[pic|[pi|[pi|[pi|[pi|[pi|[pi|[pi|[pi| |m+1 |C |[pi|[pi|… |[pi|
|] |c] |c] |c] |c] |c] |c] |c] |c] | | | |c] |c] | |c] |
|M |[pi|[pi|[pi|[pi|… |[pi|[pi| | |0 |[pi|[pi|[pi|… |[pi|
| |c] |c] |c] |c] | |c] |c] | | | |c] |c] |c] | |c] |
|m+1 |– |– |[pi|[pi|… |[pi|[pi|– | |1 |[pi|[pi|[pi|… |[pi|
| | | |c] |c] | |c] |c] | | | |c] |c] |c] | |c] |
| | | | | | | | | | |2 |[pi|[pi|[pi|… |[pi|
| | | | | | | | | | | |c] |c] |c] | |c] |
| | | | | | | | | | |… |… |… |… |… |… |Краткое описание алгоритма.
1. Нулевая итерация:
а) составляется вспомогательная табл. 6.2, в которую вносятся параметры
задачи; дополнительная строка таблицы с номером ? заполняется по мере
выполнения ?-й итерации;
б) составляется основная табл. 6.1 с номером 0, в которой заполняются
первые m строк, за исключением последних двух столбцов Аk и t. Элементы
[pic] и [pic] определяются скалярными произведениями (Cx, ej) и (Cx, B)
соответственно. Нулевая итерация заканчивается заполнением нулевой
дополнительной строки вспомогательной таблицы с оценками [pic].
2. (?+1)-я итерация.
Пусть ?-я итерация закончена. В результате заполнена ?-я основная
таблица, за исключением двух последних столбцов, и ?-я дополнительная
строка вспомогательной таблицы. Просматривается эта строка. Если все [pic],
то опорный план [pic]- решение задачи. Если хотя бы одна [pic], то в базис
вводится вектор Аk с [pic] (обычно [pic]). После этого заполняется столбец
[pic] основной таблицы. В позицию (m+1) этого столбца заносится оценка
[pic] вектора Аk. Остальные элементы этого столбца равны
[pic].
Возможны два случая:
1) все [pic] — задача неразрешима;
2) [pic] хотя бы для одного i. В этом случае, также как и в первом
алгоритме, заполняется столбец (t) основной таблицы ?, определяется
разрешающий элемент [pic]. Главная часть заполняется по рекуррентной
формуле (6.3). Заполняется (?+1)-я дополнительная строка
вспомогательной таблицы. На этом заканчивается (?+1)-я итерация.Решение М-задачи
Таблица 6.3
[pic]
Таблица 6.4[pic]
Задача (5.4), (5.5) имеет опорный план
Х0 = (0, 0, 0, [pic], [pic], [pic], [pic], 0 , [pic]) с базисом [pic].
Следовательно, [pic]. Процесс решения М-задачи вторым алгоритмом приведен в
основной табл. 6.3 и вспомогательной табл. 6.4.Решение М-задачи получено за 5 шагов. Оптимальный план ее равен [pic] и
[pic]. В оптимальном плане М-задачи искусственная переменная х9 = 0,
поэтому [pic] — решение задачи (2.12), (2.13) и [pic].
Окончательное решение задачи определения плана смешения компонентов
полностью повторяет решение, рассмотренное в завершающей части п.4 (см.
стр.11-12).7. Формирование двойственной задачи
Произвольной задаче линейного программирования определенным образом
соответствует некоторая другая задача линейного программирования. Будем
называть ее двойственной, а первоначальную задачу – исходной.
Обозначим
[pic]; [pic]; [pic]; [pic]; [pic] (7.1)
Теперь исходная задача (2.1) — (2.3) в канонической форме может быть
записана в матричном виде следующим образом.
Требуется определить вектор [pic], обращающий в максимум
[pic]. (7.2)
при условиях
AX=B; (7.3)
[pic]. (7.4)
Тогда двойственная задача – определить вектор [pic], обращающий в
минимум
f(Y)=YB (7.5)
при условиях
[pic]. (7.6)
Транспонируя обе части неравенства (7.6), записанного в виде строки, и
учитывая [pic], получим
[pic]. (7.7)
Отметим, что в двойственной задаче переменные yi могут быть и
отрицательными.Рассмотрим в качестве исходной задачу (2.12), (2.13). С учетом (7.1) и
(7.7) запишемС = (120, 100, 150, 0, 0, 0, 0, 0), B = ([pic], [pic], [pic], [pic],
[pic]),
[pic]
[pic].Двойственная задача имеет вид
[pic]; (7.8)
[pic] (7.9)8. Формирование оптимального решения двойственной задачи на основе
теоремы о двойственностиОказывается, что для задач (7.2) — (7.4) и (7.5), (7.6), называемых
двойственной парой, справедлива следующая теорема.Теорема (первая теорема о двойственности). Если одна из задач
двойственной пары (7.2) — (7.4) и (7.5), (7.6) имеет решение, то другая
задача также разрешима. При этом для любых оптимальных планов [pic] и
[pic](здесь Мх, Му – множества планов соответственно прямой и двойственной
задач) задач (7.2) — (7.4) и (7.5), (7.6) имеет место равенство
[pic].
Если линейная форма одной из задач не ограничена (для F(X) – сверху,
для f(Y) — снизу), то другая задача не имеет ни одного плана.Оптимальное решение двойственной задачи может быть найдено на основе
следующего следствия из этой теоремы.Следствие. Если вектор [pic] является оптимальным опорным планом задачи
(7.2) — (7.4), то вектор [pic] (8.1), является оптимальным опорным планом
задачи (7.5), (7.6).Стоит отметить, что в ходе решения исходной задачи вторым алгоритмом,
при каждом шаге вычисляется вектор [pic]. И если Х – оптимальный опорный
план задачи (7.2) — (7.4), то в (m+1)-й строке, соответствующей основной
таблице, находится решение задачи (7.5), (7.6).Пусть двойственная задача имеет вид (7.8), (7.9).
Так как исходная задача (2.12), (2.13) имеет решение, то на основании
рассмотренной теоремы о двойственности двойственная задача также разрешима.
Оптимальным опорным планом исходной является [pic] (см. п.4, п.6). При
этом
[pic];
; [pic].
Вычислим
[pic].На основании следствия из теоремы о двойственности можно заключить, что
[pic] является оптимальным планом двойственной задачи, при котором [pic].
Анализируя (m+1)-ю строку основной таблицы (см. табл. 6.3, шаг 5), можно
убедиться в том, что оптимальный план двойственной задачи, сформированный
на основе теоремы о двойственности, совпадает с оптимальным планом,
найденном при решении исходной задачи вторым алгоритмом симплекс-метода.
Это говорит о том, что оптимальный план задачи (7.8) — (7.9) найден верно.9. Анализ результатов и выводы
В данной работе рассматриваются два способа решения исходной задачи
линейного программирования.
Первый заключается в том, что сначала решается вспомогательная задача
(L-задача), позволяющая построить начальный опорный план, затем на основе
этого найденного плана решается исходная задача (определяется ее
оптимальный план). Второй способ является объединением двух этапов и
состоит в решении расширенной задачи (M-задачи), также приводящей к
нахождению оптимального плана исходной задачи.
Вычислительную основу этих двух способов решения составляют
соответственно первый и второй алгоритмы симплекс-метода. Один из
параметров, по которому может быть оценен любой итерационный алгоритм –
количество шагов, приводящих к решению задачи или установлению ее
неразрешимости. Для данной задачи наиболее эффективным методом оказался
первый метод(L-задача + исходная задача), т.к. он привел к решению за 4
шага, а второй метод (M-задача) за 5 шагов. Разница в числе шагов,
вероятно, обусловлена неоднозначность выбора разрешающего элемента в
исходной таблице L-задачи (3.2.1).
Сравнение количества вычислений на каждой итерации приводит к
следующим оценочным результатам рассматриваемых алгоритмов.
Преимущественная часть вычислений на каждом шаге алгоритмов определяется
размерностью главной части таблицы (в первом алгоритме) или основной
таблицы (во втором алгоритме). В первом случае она имеет размерность
(m+1)x(n+1), во втором — (m+1)x(m+1). Даже учитывая, что второй алгоритм
требует построения вспомогательной таблицы, он оказывается более
компактным.
Еще одно несомненное достоинство второго алгоритма заключается в
возможности определения оптимального плана двойственной задачи из (m+1)-й
строки основной таблицы, соответствующей последней итерации, без всяких
дополнительных вычислений.
————————
[pic]
