Читайте также:
|
|
(метод больших штрафов)
В этом методе ограничения изменяются введением искусственных переменных таким образом, чтобы экстремальная точка новой задачи находилась достаточно легко. Каждой искусственной переменной назначается большой положительный штраф М с тем, чтобы в оптимальном решении полученной задачи значение этой переменной было равно нулю.
Решим прямую задачу линейного программирования симплексным М-методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции
F(X) = 2x1+x2+3x3 при следующих условиях-ограничений (см. также M-задача).
x1+2x2+x3≤1000
3x1+5x2+2x3≤1500
x1≥100
x2≥100
x3≥200
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 200
Введем искусственные переменные x.
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 200
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1+x2+3x3 - Mx9 - Mx10 - Mx11 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x9 = 100-x1+x6
x10 = 100-x2+x7
x11 = 200-x3+x8
которые подставим в целевую функцию:
F(X) = 2x1 + x2 + 3x3 - M(100-x1+x6) - M(100-x2+x7) - M(200-x3+x8) => max
или
F(X) = (2+1M)x1+(1+1M)x2+(3+1M)x3+(-1M)x6+(-1M)x7+(-1M)x8+(-400M) => max
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x9, x10, x11,
Переходим к основному алгоритму симплекс-метода.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | min |
0 | x4 | 1000 | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1000 |
x5 | 1500 | 3 | 5 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 750 | |
x9 | 100 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 0 | |
x10 | 100 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | |
x11 | 200 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 200 | |
Индексная строка | F(X1) | -400M | -2-1M | -1-1M | -3-1M | 0 | 0 | 1M | 1M | 1M | 0 | 0 | 0 | 0 |
Иногда такую таблицу представляют с дополнительной строкой для М.
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
x4 | |||||||||||||
x5 | |||||||||||||
x9 | -1 | ||||||||||||
x10 | -1 | ||||||||||||
x11 | -1 | ||||||||||||
Индексная строка | F(X0) | -2 | -1 | -3 | |||||||||
M | -400 | -1 | -1 | -1 |
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | min |
1 | x4 | 800 | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | -1 | 800 |
x5 | 1100 | 3 | 5 | 0 | 0 | 1 | 0 | 0 | 2 | 0 | 0 | -2 | 366.67 | |
x9 | 100 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 100 | |
x10 | 100 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | |
x3 | 200 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | |
Индексная строка | F(X2) | 600-200M | -2-1M | -1-1M | 0 | 0 | 0 | 1M | 1M | -3 | 0 | 0 | 3+1M | 0 |
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | min |
x4 | -1 | -1 | ||||||||||||
x5 | -3 | -2 | ||||||||||||
x1 | -1 | |||||||||||||
x10 | -1 | |||||||||||||
x3 | -1 | |||||||||||||
Индексная строка | F(X3) | 800-100M | -1-1M | -2 | 1M | -3 | 2+1M | 3+1M |
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | min |
3 | x4 | 500 | 0 | 0 | 0 | 1 | 0 | 1 | 2 | 1 | -1 | -2 | -1 | 500 |
x5 | 300 | 0 | 0 | 0 | 0 | 1 | 3 | 5 | 2 | -3 | -5 | -2 | 150 | |
x1 | 100 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | 0 | |
x2 | 100 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | |
x3 | 200 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | |
Индексная строка | F(X4) | 900 | 0 | 0 | 0 | 0 | 0 | -2 | -1 | -3 | 2+1M | 1+1M | 3+1M | 0 |
План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
4 | x4 | 350 | 0 | 0 | 0 | 1 | -0.5 | -0.5 | -0.5 | 0 | 0.5 | 0.5 | 0 |
x8 | 150 | 0 | 0 | 0 | 0 | 0.5 | 1.5 | 2.5 | 1 | -1.5 | -2.5 | -1 | |
x1 | 100 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | 0 | |
x2 | 100 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | |
x3 | 350 | 0 | 0 | 1 | 0 | 0.5 | 1.5 | 2.5 | 0 | -1.5 | -2.5 | 0 | |
Индексная строка | F(X5) | 1350 | 0 | 0 | 0 | 0 | 1.5 | 2.5 | 6.5 | 0 | -2.5+1M | -6.5+1M | 1M |
Оптимальный план можно записать так:
x4 = 350
x8 = 150
x1 = 100
x2 = 100
x3 = 350
F(X) = 2*100 + 1*100 + 3*350 = 1350
Южный филиал Национального университета
Дата добавления: 2014-12-15; просмотров: 37 | Поможем написать вашу работу | Нарушение авторских прав |