4.3 Решение двойственным симплекс-методом.
Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами. В обычном симплексном алгоритме план всегда должен быть допустимым. Допустимый план — это такой план, который удовлетворяет всем ограничениям задачи при обязательном условии не отрицательности неизвестных, то есть любые числа в итоговом столбце положительны. План называется недопустимым (или условно-оптимальным), если в итоговом столбце имеются отрицательные числа, зато оценки целевой строки соответствуют целевой функции, то есть являются положительными при решении на максимум и отрицательными при решении на минимум. В процессе решения двойственным методом план является недопустимым. При использовании двойственного метода сначала применяют обычную симплекс-процедуру и добиваются того, чтобы все оценки соответствовали цели решения задачи, причем пока не обращают внимания на знаки чисел в итоговом столбце. Только когда такой условно-допустимый план достигнут, смотрят на эти знаки. Если в итоговом столбце оказались отрицательные числа, план изменяется так, чтобы недопустимость уменьшилась, а затем и исчезла, но чтобы двойственные оценки продолжали соответствовать при этом цели решения задачи. Возможность придавать в процессе решения отрицательные значения неизвестным, входящим в план, в случае, если ограничения заданы неравенствами, позволяет избавиться от искусственных неизвестных, это сокращает размеры задачи, а значит, и вычислений [6].
Для удобного представление решения используется программа для работы с электронными таблицами MS Excel.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
Определим минимальное значение целевой функции
при следующих условиях-ограничений:
Введем искусственные переменные x: в 1-м равенстве вводим переменную x4; в 2-м равенстве вводим переменную x5;
Для постановки задачи на минимум целевую функцию запишем так:
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
которые подставим в целевую функцию:
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x4, x5
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,30,6)
Базисное решение называется допустимым, если оно неотрицательно.
Переходим к основному алгоритму симплекс-метода.
Проводим итерацию №0 для проверки критерия оптимальности.
Проверка критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент.
Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (30 : 6 , 6 : 1 ) = 5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (6) и находится на пересечении ведущего столбца и ведущей строки (Таблица 6).
Таблица 6 – Симплекс-таблица с выделенным разрешающим элементом
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x4 |
30 |
5 |
4 |
6 |
1 |
0 |
|
x5 |
6 |
1 |
1 |
1 |
0 |
1 |
|
F(X1) |
36M |
-3+6M |
-4+5M |
-2+7M |
0 |
0 |
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент 6
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент.
Проводим пересчет симплекс-таблицу по разрешающему элементу (Таблица 7).
Таблица 7 – Симплекс-таблица после совершения итерации №0
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
5 |
5/6 |
2/3 |
1 |
1/6 |
0 |
|
x5 |
1 |
1/6 |
1/3 |
0 |
-1/6 |
1 |
|
F(X1) |
10+M |
-11/3+M |
-22/3+M |
0 |
1/3-11/6M |
0 |
Проводим итерацию №1 для проверки критерия оптимальности.
Текущий опорный план не оптимален, так как в индексной строке находятся положительные коэффициенты.
Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.
Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (5 : 2/3 , 1 : 1/3 ) = 3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1/3) и находится на пересечении ведущего столбца и ведущей строки. (Таблица 8)
Таблица 8 – Симплекс-таблица с выделенным разрешающим элементом
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
5 |
5/6 |
2/3 |
1 |
1/6 |
0 |
|
x5 |
1 |
1/6 |
1/3 |
0 |
-1/6 |
1 |
|
F(X2) |
10+M |
-11/3+M |
-22/3+M |
0 |
1/3-11/6M |
0 |
Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент 1/3
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-таблицу:
Таблица 9 – Симплекс-таблица после совершения итерации №1
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
3 |
1/2 |
0 |
1 |
1/2 |
-2 |
|
x2 |
3 |
1/2 |
1 |
0 |
-1/2 |
3 |
|
F(X2) |
18 |
0 |
0 |
0 |
-1-M |
8-M |
Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Таблица 10 – Окончательный вариант симплекс-таблицы
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
x3 |
3 |
1/2 |
0 |
1 |
1/2 |
-2 |
|
x2 |
3 |
1/2 |
1 |
0 |
-1/2 |
3 |
|
F(X2) |
18 |
0 |
0 |
0 |
-1-M |
8-M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
Заключение
Целью курсовой работы была проверка и применение теоретических знаний полученных за курс по дисциплине «Методы оптимизации». Объектом исследования была задача «О распределении» с необходимостью найти оптимальный план распределения, при ограниченных средствах и времени. Были применены основные методы для решения поставленной задачи, такие как: симплекс-метод, метод Гомори и двойственный симплекс-метод. Для удобного представление решения используется программа для работы с электронными таблицами MS Excel. Был построен оптимальный план.
Библиографический список
1. Теория принятия решений: задачи нелинейной оптимизации: учеб. пособие / А. В. Зыкина ; ОмГТУ. - Омск : Изд-во ОмГТУ, 2008. - 59 с;
2. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации; Покорный Ю.В. Оптимальные задачи – М.: ФИЗМАТЛИТ, 2011. – 368 с; 3. Азарнова Т.В., Каширина И.Л., Чернышова Г.Д. Методы оптимизации: Учебное пособие. - Воронеж: Изд-во ВГУ, 2003. - 87 с;
4. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ — М.: Мир, 1985. – 320 с; 5. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения — М.: Радио и связь, 1992. — 504 с;
6. Азарнова Т.В., Каширина И.Л., Чернышова Г.Д. Методы оптимизации: Учебное пособие. - Воронеж: Изд-во ВГУ, 2003. - 87 с.