Симплекс-метод

  • 05 дек. 2012 г.
  • 999 Слова
Пример расчет пространства симплекс методом.
Находится максимум n-мерного пространства.







«Исследование операций»


Решение задач линейного программирования
симплексным методомМосква, 2012

Найти max L(x) = max (2X1 + 5X2 + 2X3) при условиях:

1X1 + 3X2 + 4X3 ≤ 21

2X1 + 6X2 + 4X3 ≤ 20

3X1 + 6X2 + 7X3 ≤ 23

X1..3≥ 0

Этап 1. Подготовка и формулировка исходной симплексной таблицы.

Приведём задачу ЛП к канонической форме:

1X1 + 3X2 + 4X3 + X4 = 21

2X1 + 6X2 + 4X3 + X5 = 20

3X1 + 6X2 + 7X3 + X6= 23

X1..6 ≥ 0

Количество переменных: n = 6
Количество уравнений: m = 3

Представление функций L(x) и V(x) в неявной форме:

0 = L - 2X1 - 5X2 - 2X3

-64 = V – 6X1 - 15X2 - 15X3 -X4 - X5 - X6

Составим симплексную таблицу из m + 2 = 5 строк:

N |Б |D0 |D1 |D2 |D3 |D4 |D5 |D6 | |1 |7 |21 |1 |3 |4 |1 |0 |0 | |2 |8 |20 |2 |6 |4 |0 |1 |0 | |3 |9 |23 |3 |6 |7 |0 |0 |1 | |4 |E |0|-2 |-5 |-2 |0 |0 |0 | |5 |E |-64 |-6 |-15 |-15 |-1 |-1 |-1 | |







Этап 2. Формирование исходного опорного плана задачи ЛП на основе решения вспомогательной задачи.

K = arg { j }min dm+2,j
R = dm+2,K; j = 1..n
l = arg { i } min (di0 / diK)

Итерация 1.

K = 2
R = -15 < 0 => Переходим к определению l
l = 2

Выведем из базиса переменную Xl и введём в него переменнуюXk. Элементы строки l = 2 симплексной таблицы преобразуем по правилу: dlj := dlj / dlk ; j = 0..n
Остальные элементы симплексной таблицы преобразуем по правилу:
dij :=dij – dlj * dik ; i = 1..m+2 ;j = 0..n ; i < > 2; Bl := 2

N |Б |D0 |D1 |D2 |D3 |D4 |D5 |D6 | |1 |7 |11 |0 |0 |2 |1 |-0,5 |0 | |2 |2 |3,333333 |0,333333 |1 |0,666667 |0 |0,166667 |0 | |3 |9 |3 |1 |0 |3 |0 |-1 |1 | |4 |E|16,66667 |-0,33333 |0 |1,333333 |0 |0,833333 |0 | |5 |E |-17,3333 |-1,33333 |0 |-5,66667 |-1 |1,333333 |-1 | |



Итерация 2.

K = 3
R = -5,66 < 0 => Переходим к определению l
l = 3

Выведем...
tracking img