Нет комментариев 26.12.2005

В прошлом примере мы разобрали пошаговое решение простой задачи линейного программирования в каноническом виде с неотрицательной правой частью в неравенствах ограничений. Рассмотрим более общий случай:

4х1 + 15х2 + 12х3 + 2х4 -> min

2x2 + 3x3 + x4 >= 1
x1 + 3x2 + x3 - x4 >= 0
x1, x2, x3, x4 >=0

Приведем задачу в следующий вид:

-4х1 - 15х2 - 12х3 - 2х4 -> max

-2x2 - 3x3 - x4 <= -1
-x1 - 3x2 - x3 + x4 <= 0
x1, x2, x3, x4 >=0

Введем переменные S1, S2 >= 0, тогда задача примет стандартный (канонический) вид:

-4х1 - 15х2 - 12х3 - 2х4 -> max

0x1 - 2x2 - 3x3 - x4 + 1s1 + 0s2 = -1
-x1 - 3x2 - x3 + x4 + 0s1 + 1s2 = 0
x1, x2, x3, x4, s1, s2 >=0

Составим симплекс таблицу (кликните для увеличения):

1 шаг: В строке Cj выписываем коэффициенты целевой функции при переменных x1, x2, x3, x4, s1, s2. В строках 1,2 - коэффициенты при соответсвующих переменных из уравнений ограничений. В столбце RHS (right hand side), в строках 1, 2 пишем числа -1 и 0 из правой части уравнений ограничений. Переменные, образующие единичную матрицу (выделена бежевым) будем называть базисными, в данном случае s1 и s2.

2 шаг: Заполняем столбец CB строки 1, 2 коэффициентами целевой функции при базисных переменных, то есть 0 при s1 в строке 1 (пересечение строки 1 и столбца s1) и 0 при s2 в строке 2.

3 шаг: заполняем строку 3 (Zj) путем перемножения каждого элемента столбца CB на соответствующие элементы строк 1, 2 и сложением. То есть первый элемент строки Zj получается как: 0*0 + 0*(-1) = 0. Второй как 0*(-2)+0*(-3). В данном случае все элементы строки получаются равными 0. Аналогично получается 0 в столбце RHS.

4 шаг: строка 4 (Cj - Zj) получается почленным вычитанием элементов строки 3 (Zj) из элементов строки Cj (всегда из верхней строки на всех шагах).

5 шаг: Смотрим на элементы RHS выше строки Zj (у нас на строки 1 и 2). Если все элементы RHS неотрицательные, то идем на шаг 5". Если есть хоть один отрицательный элемент, идем на шаг 5'.

5' шаг: В каждой строке 1 и 2 вычисляем соотношения RHS/x, где x пробегает значения той же строки, что и RHS, столбцы x1, x2, x3, x4, s1, s2. Мы ищем МИНИМАЛЬНЫЙ СТРОГОПОЛОЖИТЕЛЬНЫЙ ЭЛЕМЕНТ среди получившихся чисел (то есть мы можем вычислять RHS/x только для х того же знака, что и RHS). В нашем случае:
Строка 1:
столбец х2: (-1)/(-2)=0,5; столбец х3: (-1)/(-3)=0,3333(3); столбец х4: (-1)/(-1)=1;
Строка 2: все соотношения равны нулю.
Минимальный строгоположительный элемент получился в столбце x3. Этот элемент назовем ведущим, у нас -3. В таблице он выделен зеленым цветом. Строка и столбец, содержащие этот элемент называются ведущими.
Идем на шаг 7.

7 шаг: Формируем строки 5, 6 путем деления ведущей строки на ведущий элемент и формирования единичного столбца на месте ведущего). Не забываем RHS.

Сделаем совместно еще одну итерацию. На предыдущем шаге мы заполнили строки 5, 6. Далее выполняем последовательно шаг 2, шаг 3 и шаг 4, получаем новую строку (Cj - Zj), у нас строка 8. Идем на шаг 5 - на второй итерации у нас RHS в строках 5, 6 >0 , значит идем на шаг 5".

5" шаг: Ищем в строке 8 (Cj - Zj) МАКСИМАЛЬНЫЙ СТРОГОПОЛОЖИТЕЛЬНЫЙ элемент. Если такой есть, то ему соответствует ведущий стролбец (у нас x4). Идем на шаг 6. Если в (Cj - Zj) нет строгоположительных элементов, то идем в конец.

6 шаг: Ищем в ведущем столбце МИНИМАЛЬНО ПОЛОЖИТЕЛЬНОЕ число из формулы (RHS/ведущий столбец). То есть, в данном случае, выбираем между 0,33/0,33=1 и 0,33/1,33=0,25. Найдя такое число, определяем ведущую строку, у нас строка 6. Пересечение ведущих столбца и строки дает нам ведущий элемент, в нашем случае 1,33 (выделен зеленым). Идем на шаг 7.

Конец: итерации продолжаются до тех пор (в случае, что оптимальное решение задачи существует), пока на шаге 5' или на шагах 5" и 6 мы не сможем отыскать положительного ведущего элемента.

В нашем примере:
Мы сформировали строки 9, 10, 11. RHS (строки 9, 10) неотрицательна, следовательно идем на шаг 5". Число 3,50 - максимальный строгоположительный элемент (стролбец s1), но положительного ведущего элемента в этой строке нет.
Тогда в строке Zj (у нас строка 11) в RHS - столбце получим значение целевой функции в оптимальной точке (x3, x4) = (0,25; 0,25) равное -3,5. Значения 0,25 и 0,25 получаем из RHS в строках 9, 10.

Жми!

 Loading ...