|
Реферат: Решение задач линейного программирования (Математика)
ЛАБОРАТОРНАЯ РАБОТА № 11
РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Цель работы: изучение принципов составления оценочных характеристик
для задач линейного программирования, получение навыков использования
симплекс-метода для решения задач линейного программирования, усвоение
различий получаемых результатов, изучение табличной формы применения
симплекс-метода.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
Стандартная задача линейного программирования состоит из трех частей:
целевой функции (на максимум или минимум) - формула (1.1), основных
oграничений [pic] - формула (1.2), ограничений не отрицательности
переменных (есть, нет) - формула (1.3)
(1.1)
[pic] i = 1,… m
(1.2)
[pic]
(1.3)
Алгоритм решения задач линейного программирования требует приведения их
постановки в канонический вид, когда целевая функция стремится к максимуму
(если стремилась к минимуму, то функцию надо умножить на -1, на станет
стремиться к максимуму), основные ограничения имеют вид равенства (для
приведения к равенствам в случае знака [pic] надо в правую часть каждогo
такого k-го неравенства добавить искусственную переменную uk [pic], а в
случае знака [pic], uk [pic] надо отнять ее из правой части основных
ограничений), присутствуют ограничения не отрицательности переменных (если
их нет для некоей переменной хk, то их можно ввести путем замены всех
вхождений этой
переменной комбинацией x1k - х2k = хk, где х1k [pic] и х2k [pic]). При
этом для решения задачи линейного программирования необходимо иметь базис,
т.е. набор переменных хi, в количестве, равным числу основных ограничений,
причем чтобы каждая из этих переменных присутствовала лишь в одном основном
oграничении и имела свой множитель аij = 1. Если таких переменных нет, то
они искусственно добавляются в основные ограничения и получают индексы
хm+1, xm+2 и т.д. Считается при этом, что они удовлетворяют условиям не
отрицательности переменных. Заметим, что если базисные переменные (все)
образуются в результате приведения задачи к каноническому виду, то целевая
функция задачи остается без изменений, а если переменные добавляются
искусственно к основным ограничениям, имеющим вид равенств, то из целевой
функции вычитается их сумма, умноженная на М, т.е. [pic] (так называемый
модифицированный симплекс-метод). Мы не будем рассматривать задачи,
относящиеся к модифицированному симплекс-методу. Для практической рабо-ты
по нахождению решения задачи линейного программирования (по варианту
простого симплекс-метода) будут использоваться алгоритм итерационного
(многошагового) процесса нахождения решения и два типа оперативных оце-нок,
позволяющих делать переходы от одного шага к другому, а также показы-
вающих, когда итерационный процесс остановится и результат будет найден.
Первая оценка - это дельта-оценка, для переменной хj она имеет вид:
[pic]
(1.4)
Здесь выражение i [pic] B означает, что в качестве коэффициентов целевой
функ-ции, представленных в сумме выражения (1.4), используются коэффициенты
переменных, входящих в базис на данном шаге итерационного процесса. Пере-
менными аij являются множители матрицы коэффициентов А при основных ог-
раничениях, рассчитанные на данном шаге итерационного процесса. Дельта-
оценки рассчитываются по всем переменным хi, имеющимся в задаче. Следует
отметить; что дельта-оценки базисных переменных равны нулю. После нахож-
дения дельта-оценок из них выбирается наибольшая по модулю отрицательная
оценка, переменная хk, ей соответствующая, будет вводиться в базис. Другой
важной оценкой является тетта-оценка, имеющая вид:
[pic]
(1.5)
Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере-
менную хk и элементы столбца ХB делим на соответствующие (только положи
тельные) элементы столбца матрицы А, соответствующего переменой xk. Из
полученных результатов выбираем минимальный, он и будет тетта-оценкой, аi-й
элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выво-
диться из базиса, заменяясь элементом xk, полученным по дельта-оценке. Для
осуществления такой замены нужно в i-ой строке k - гo столбца матрицы А сде-
лать единицу, а в остальных элементах k-го столбца сделать нули. Такое
преоб-разование и будет одним шагом итерационного процесса. Для
осуществления такого преобразования используется метод Гаусса. В
соответствии с ним i-я строка всей матрицы А, а также i-я координата ХB
делятся на aik (получаем единицу в i-ой строке вводимого в базис элемента).
Затем вся i-я строка (если i не единица), а также i-я координата ХB
умножаются на элемент (-а1k). После этого производится поэлементное
суммирование чисел в соответствующих столбцах 1-ой и i-ой строк,
суммируются также ХB1, и (-а1k)*ХBi;. Аналогичные действия производятся для
всех остальных строк кроме i-ой (базисной) строки. В результате получается,
что в i-ой строке k-го элемента стоит 1, а во всех ос-тальных его строках
находится 0. Таким образом осуществляется шаг итерационального алгоритма,
Шаги алгоритма симплекс-метода продолжаются до тех пор, пока не будет
получен один из следующих результатов.
• Все небазисные дельта-оценки больше нуля — найдено решение задачи ли-
нейного программирования, оно представляет из себя вектор компонент х;,
значения которых либо равны нулю, либо равны элементам столбца Х, та-в
кие компоненты стоят на базисных местах (скажем, если базис образуют пе-
ременные х2, x4, х5, то ненулевые компоненты стоят в векторе решения зада-
чи линейного программирования на 2-м, 4-м и 5-м местах).
• Имеются небазисные дельта-оценки, равные нулю, тогда делается вывод о
том, что задача линейного программирования имеет бесчисленное множество
решений (представляемое лучом или отрезком). Подробно рассматривать случаи
такого типа, а также отличия между решениями в виде луча и отрезка мы не
будем.
• Возможен вариант получения столбца отрицательных элементов на отрица-
тельной рассчитанной дельта-оценке, в такой ситуации нельзя вычислить
тетта-оценки. В этом случае делается вывод, что система ограничений задачи
линейного программирования несовместна; следовательно, задача линейного
программирования не имеет решения.
Решение задачи линейного программирования, если оно единственное, следует
записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой
функ-ции в точке решения L*(Х*). В других случаях (решений много или они
отсут-ствуют) следует словесно описать полученную ситуацию. Если решение
задачи линейного программирования не будет получено в течение 10-12
итераций симплекс-метода, то следует написать, что решение отсутствует в
связи с неог-рачниченностью функции цели.
Для практического решения задачи линейного программирования симплекс-
методом удобно пользоваться таблицей вида (табл. 11.1):
Таблица 1.1
|B |CB |XB |A1 |… |An |? |
|Базисные |Целевые |Правые | | | | |
|компоненты |Коэффиц. |Части | | | | |
| |Базиса |ограничен | | | | |
|? | | |?1 | |?n | |
Задание
Необходимо решить задачу линейного программирования.
L(x) = x1 – 2x2 + 3x3 [pic]
x1 – 3x2 [pic] 3
2x1 – x2 + x3 [pic] 3
-x1 + 2x2 – 5x3 [pic] 3
Все xi [pic] 0 i = 1, …3
1. Для начала приведем задачу к каноническому виду:
L(x) = x1 – 2x2 + 3x3 [pic]
x1 – 3x2 + x4 = 3
2x1 – x2 + x3 + x5 = 3
-x1 + 2x2 – 5x3 + x6 = 3
Все xi [pic] 0 i = 1, …6
2. Составляем таблицу симплекс-метода (табл. 1.2). Видно, что базис
образуют компаненты x4, x5, x6:
|B |CB |XB |A1 |A2 |A3 |A4 |A5 |A6 |? |
|A4 |0 |3 |1 |-3 |0 |1 |0 |0 |- |
|A5 |0 |3 |2 |-1 |1 |0 |1 |0 |3 |
|A6 |0 |3 |-1 |2 |-5 |0 |0 |1 |- |
|? | | |-1 |2 |-3 |0 |0 |0 | |
|A4 |0 |3 |1 |-3 |0 |1 |0 |0 | |
|A3 |3 |3 |2 |-1 |1 |0 |1 |0 | |
|A6 |0 |3 |-1 |2 |0 |0 |0 |1 | |
|? | |9 |5 |2 |0 |0 |3 |0 | |
Таким образом, уже на втором шаге расчетов (вычислений дельта-оценок)
получено, что все небазисные дельта оценки положительны, а это означает,
что данная задача имеет единственное решение:
3. Решение задачи запишем в виде:
X* = (0, 0, 3, 3 ,0, 3), L*(X*) = 9.
-----------------------
[pic]
[pic]
Министерство общего и профессионального образования
Российской Федерации
Воронежский Государственный Архитектурно – Строительный
Университет
Кафедра Экономики и управления строительством
ЛАБОРАТОРНАЯ РАБОТА
На тему: «Решение задач линейного программирования»
| |Выполнил: |
| |Студент 4 курса |
| |ФЗО ЭУС |
| |Сидоров В.В. |
| | |
| |Руководитель: |
| |Богданов Д. А. |
Воронеж – 2002 г.
Реферат на тему: Решение задач линейной оптимизации симплекс – методом
Министерство образования РФ и РТ.
Казанский Государственный Университет им. А.Н. Туполева.
_______________________________________________
Курсовая работа по дисциплине
«Численные методы оптимизации»
Решение задач линейной оптимизации симплекс – методом.
Выполнил: ст.гр.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]
| |
