Введение
Двойственный симплекс-метод
можно применять при решении задачи линейного
программирования, свободные члены системы
уравнений которой могут быть любыми числами.
В обычном симплексном алгоритме план
всегда должен быть допустимым.
Допустимый план — это такой
план, который удовлетворяет всем ограничениям
задачи при обязательном условии неотрицательности
неизвестных, то есть любые числа в итоговом
столбце положительны. План называется
недопустимым (или условно-оптимальным),
если в итоговом столбце имеются отрицательные
числа, зато оценки целевой строки соответствуют
целевой функции, то есть являются положительными
при решении на максимум и отрицательными
при решении на минимум.
В процессе решения
двойственным методом план является
недопустимым. При использовании
двойственного метода сначала
применяют обычную симплекс-процедуру
и добиваются того, чтобы все оценки соответствовали
цели решения задачи, причем пока не обращают
внимания на знаки чисел в итоговом столбце.
Только когда такой условно-допустимый
план достигнут, смотрят на эти знаки.
Если в итоговом столбце оказались отрицательные
числа, план изменяется так, чтобы недопустимость
уменьшилась, а затем и исчезла, но чтобы
двойственные оценки продолжали соответствовать
при этом цели решения задачи. Возможность
придавать в процессе решения отрицательные
значения неизвестным, входящим в план,
в случае, если ограничения заданы неравенствами,
позволяет избавиться от искусственных
неизвестных, это сокращает размеры задачи,
а значит, и вычислений.
Алгоритм двойственного симлекс
метода:
1. находится план;
2. проверяют план на оптимальность;
3. если псевдоплан оптимален,
решение заканчивается, иначе устанавливается
неразрешение задачи, либо переходят который
новому псевдоплану;
4. выбирают разрешающую строку
и разрешающий столбец;
5. находят новый псевдоплан
и переходят который пункту 2
Цель курсовой работы: приобрести навыки решения
двойственно задачи с использованием
объектно-ориентированного и визуального
программирования.
1.Основная часть
1.1 Математическая
постановка задачи курсового
проекта
Двойственный симплекс
метод
Из трех видов сырья необходимо
составить смесь, в состав которой должно
входить не менее 26ед. химического вещества
А. 30ед. – вещества В и 24 ед. – вещества
С. Количество единиц химического вещества,
содержащегося в 1кг сырья каждого
вида, указанно в таблице. В ней же приведена
цена сырья каждого вида.
Вещество |
Количество единиц вещества,
содержащегося в 1 кг сырья вида |
| |
1 |
2 |
3 |
4 |
А |
1 |
1 |
- |
4 |
В |
2 |
- |
3 |
5 |
С |
1 |
2 |
4 |
6 |
Цена 1 кг сырья (руб.) |
5 |
6 |
7 |
4 |
Составить смесь, содержащую
не менее нужного количества вещества
данного вида и имеющую минимальную стоимость.
- Дать формализованное описание задачи
- Сформулировать двойственную
задачу к исходной
- Указанную задачу решить двойственным
симплекс методом
1.2 Описание метода
решения
Для упрощения процесса решения исходные
данные задачи линейного программирования
при решении ее симплекс методом записываются
в специальные симплекс-таблицы. Поэтому
одна из модификаций симплекс метода получила
название табличный симплекс
метод. Задача линейного программирования
в каноническом виде:
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn + xn+1=b1
a2,1x1+a2,2x2+...a2,nxn +xn+2 =b2
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
Исходная таблица для задачи имеет следующий
вид:
| |
x1 |
x2 |
... |
xn-1 |
xn |
b |
F |
-a0,1 |
-a0,2 |
... |
-a0,n-1 |
-a0,n |
-b0 |
xn+1 |
a1,1 |
a1,2 |
... |
a1,n-1 |
a1,n |
b1 |
xn+2 |
a2,1 |
a2,2 |
... |
a2,n-1 |
a2,n |
b2 |
... |
... |
... |
... |
... |
... |
... |
xn+m |
am,1 |
am,2 |
... |
am,n-1 |
am,n |
bm |
x1, x2, xn - исходные
переменные, xn+1, xn+2, xn+m - дополнительные
переменные. Все дополнительные переменные
мы приняли как базисные, а исходные переменные
как небазисные (дополнительные
записаны в первый столбец симплекс-таблицы
а исходные в первую строку). При каждой
итерации элементы симплекс-таблицы пересчитывают
по определенным правилам.
Алгоритм симплекс-метода.
Подготовительный
этап
Приводим задачу ЛП к каноническому виду
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn+xn+1=b1
a2,1x1+a2,2x2+...a2,nxn+xn+2=b2
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
В случае если в исходной задаче необходимо
найти минимум - знаки коэффициентов целевой
функции F меняются на противоположные
a0,n=-a0,n. Знаки коэффициентов
ограничивающих условий со знаком "≥"
так же меняются на противоположные. В
случае если условие содержит знак "≤"
- коэффициенты запишутся без изменений.
Шаг 0. Составляем
симплексную таблицу, соответствующую
исходной задаче
| |
x1 |
x2 |
... |
xn-1 |
xn |
b |
F |
-a0,1 |
-a0,2 |
... |
-a0,n-1 |
-a0,n |
-b0 |
xn+1 |
a1,1 |
a1,2 |
... |
a1,n-1 |
a1,n |
b1 |
xn+2 |
a2,1 |
a2,2 |
... |
a2,n-1 |
a2,n |
b2 |
... |
... |
... |
... |
... |
... |
... |
xn+m |
am,1 |
am,2 |
... |
am,n-1 |
am,n |
bm |
Шаг 1. Проверка
на допустимость.
Проверяем на положительность элементы
столбца b (свободные члены), если среди
них нет отрицательных то найдено допустимое
решение (решение соответствующее одной
из вершин многогранника условий) и мы
переходим к шагу 2. Если в столбце свободных
членов имеются отрицательные элементы
то выбираем среди них максимальный по
модулю - он задает ведущую строку k. В этой
строке так же находим максимальный по
модулю отрицательный элемент ak,l - он задает
ведущий столбец - l и является ведущим элементом. Переменная,
соответствующая ведущей строке исключается
из базиса, переменная соответствующая
ведущему столбцу включается в базис.
Пересчитываем симплекс-таблицу согласно правилам.
Если же среди свободных членов есть
отрицательные элементы - а в соответствующей
строке - нет то условия задачи несовместны
и решений у нее нет.
Если после перерасчета в столбце свободных
членов остались отрицательные элементы,
то переходим к первому шагу, если таких
нет, то ко второму.
Шаг 2. Проверка
на оптимальность.
На предыдущем этапе найдено допустимое
решение. Проверим его на оптимальность
Если среди элементов симплексной таблицы,
находящихся в строке F (не беря в расчет
элемент b0 - текущее значение
целевой функции) нет отрицательных, то
найдено оптимальное решение.
Если в строке F есть отрицательные элементы
то решение требует улучшения. Выбираем
среди отрицательных элементов строки
F максимальный по модулю (исключая значение
функции b0)
a0,l=min{a0,i }
l - столбец в котором он находится будет
ведущим. Для того, что бы найти ведущую
строку, находим отношение соответствующего
свободного члена и элемента из ведущего
столбца, при условии, что они неотрицательны.
bk/ak,l =min
{bi/ai,l } при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально
- ведущая. Элемент ak,l - ведущий
(разрешающий). Переменная, соответствующая
ведущей строке (xk) исключается
из базиса, переменная соответствующая
ведущему столбцу (xl) включается
в базис.
Пересчитываем симплекс-таблицу по формулам.
Если в новой таблице после перерасчета
в строке F остались отрицательные элементы
переходим к шагу 2
Если невозможно найти ведущую строку,
так как нет положительных элементов в
ведущем столбце, то функция в области
допустимых решений задачи не ограничена
- алгоритм завершает работу.
Если в строке F и в столбце свободных
членов все элементы положительные, то
найдено оптимальное решение.
1.3 Решение
задачи с помощью прямых расчетов,
согласно указанному методу.
Решим прямую задачу линейного
программирования двойственным симплексным
методом, с использованием симплексной
таблицы.
Приведем систему ограничений
к системе неравенств смысла ≤, умножив
соответствующие строки на (-1).
Определим минимальное значение
целевой функции F(X) = 5x1 + 6x2 + 7x3 + 4x4 при следующих
условиях- ограничений.
- x1 - x2 - 4x4≤-26
- 2x1 - 3x3 - 5x4≤-30
- x1 - 2x2 - 4x3 - 6x4≤-24
Для построения первого опорного
плана систему неравенств приведем к системе
уравнений путем введения дополнительных
переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤)
вводим базисную переменную x5. В 2-м неравенстве
смысла (≤) вводим базисную переменную
x6. В 3-м неравенстве смысла (≤) вводим базисную
переменную x7.
-1x1-1x2 + 0x3-4x4 + 1x5 + 0x6 + 0x7 = -26
-2x1 + 0x2-3x3-5x4 + 0x5 + 1x6 + 0x7 = -30
-1x1-2x2-4x3-6x4 + 0x5 + 0x6 + 1x7 = -24
Матрица коэффициентов A = a(ij)
этой системы уравнений имеет вид:
-1 |
-1 |
0 |
-4 |
1 |
0 |
0 |
-2 |
0 |
-3 |
-5 |
0 |
1 |
0 |
-1 |
-2 |
-4 |
-6 |
0 |
0 |
1 |
Базисные переменные это переменные,
которые входят только в одно уравнение
системы ограничений и притом с единичным
коэффициентом.
Экономический смысл дополнительных
переменных: дополнительные переменные
задачи ЛП обозначают излишки сырья, времени,
других ресурсов, остающихся в производстве
данного оптимального плана.
Решим систему уравнений относительно
базисных переменных: x5, x6, x7
Полагая, что свободные переменные
равны 0, получим первый опорный план:
X1 = (0,0,0,0,-26,-30,-24)
Базисное решение называется
допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x5 |
-26 |
-1 |
-1 |
0 |
-4 |
1 |
0 |
0 |
x6 |
-30 |
-2 |
0 |
-3 |
-5 |
0 |
1 |
0 |
x7 |
-24 |
-1 |
-2 |
-4 |
-6 |
0 |
0 |
1 |
F(X0) |
0 |
-5 |
-6 |
-7 |
-4 |
0 |
0 |
0 |
1. Проверка критерия оптимальности.
План 0 в симплексной таблице
является псевдопланом, поэтому определяем
ведущие строку и столбец.
2. Определение новой свободной
переменной.
Среди отрицательных значений
базисных переменных выбираем наибольший
по модулю.
Ведущей будет 2-ая строка, а
переменную x6 следует вывести из базиса.
3. Определение новой базисной
переменной.
Минимальное значение θ соответствует
4-му столбцу, т.е. переменную x4 необходимо
ввести в базис.
На пересечении ведущих строки
и столбца находится разрешающий элемент
(РЭ), равный (-5).
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x5 |
-26 |
-1 |
-1 |
0 |
-4 |
1 |
0 |
0 |
x6 |
-30 |
-2 |
0 |
-3 |
-5 |
0 |
1 |
0 |
x7 |
-24 |
-1 |
-2 |
-4 |
-6 |
0 |
0 |
1 |
F(X0) |
0 |
-5 |
-6 |
-7 |
-4 |
0 |
0 |
0 |
θ |
|
-5 : (-2) = 21/2 |
- |
-7 : (-3) = 21/3 |
-4 : (-5) = 4/5 |
- |
- |
- |