с использованием симплекс-таблиц

Решение задачи линейного программирования

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

где – положительные числа. Целевую функцию записываем в виде:

Из коэффициентов системы уравнений и коэффициентов целевой функции составляем первую симплекс-таблицу:

Таблица 1

Б.п	x		x		xm	x		xj			C.к
										а
xi										а
										a
f											f

Числа , ,..., ,..., называются индексами; последняя строка называется индексной.

Полагая переменные (свободные) , ...,x_n равными нулю, получим первое базисное решение (a , a , a 0...,0) и первое значение f целевой функции, соответствующее этому решению. Первый базисный план и первое значение целевой функции образуют последний правый столбец таблицы 1. В верхней нулевой строке таблицы 1 записаны все переменные задачи ЛП, в левом нулевом столбце записаны базисные переменные. Будем рассматривать задачу на максимум функции f.

Переход ко второй симплекс-таблице осуществляется следующим образом: выбираем j -й столбец (разрешающий) таблицы 1 из условия, что является наибольшим по модулю отрицательным индексом и хотя бы один из элементов a >0;

выбираем i -ю строку (разрешающую) из условия, что:

a / a = для a >0,

принимая a в качестве разрешающего элемента, производим преобразование коэффициентов таблицы (в том числе элементов индексной строки) так, как это делается при решении системы уравнений методом Жордана-Гаусса:

Таким образом, осуществляется переход от одного базисного решения системы ограничений к другому, от одной системы уравнений к другой, ей эквивалентной. При этом после преобразования в индексной строке получаются индексы, соответствующие новым свободным переменным. Переход к следующей таблице (если это необходимо) осуществляется аналогичным образом.

Сформулируем критерий оптимальности решения задачи ЛП с использованием симплекс-таблиц.

Если в очередной симплекс-таблице:

1) найдется хотя бы один отрицательный индекс и в каждом столбце с отрицательным индексом окажется хотя бы один положительный элемент, то план можно улучшить, перейдя к следующей симплекс-таблице;

2) найдется хотя бы один отрицательный индекс и все элементы в столбце, содержащем этот индекс отрицательные, то

fmax =+

3) нет ни одного отрицательного индекса, то достигнут оптимальный план.

Пример. Найти наибольшее значение функции f = 5 x + 2 x , если x , x неотрицательные и удовлетворяют системе неравенств:

Решение. Вводим балансовые переменные х₃, x , x и получаем систему уравнений:

Целевую функцию представим в форме: f =0 - (-5x - 2х ). Составляем первую симплекс-таблицу 2:

Таблица 2

Б.п.						с.к.
	-2
		-1
f	-5	-2

В качестве разрешающего столбца выбираем первый столбец, ибо = -5- наибольший по модулю отрицательный индекс. В качестве разрешающей выбираем третью строку, так как min .

Значит, разрешающим элементом является элемент а = 1. Переменная х переводится в состав базисных вместо х .Элементы разрешающей строки делим на 1(они не изменятся), элементы разрешающего столбца, кроме а , заменяем нулями. Все другие элементы преобразуем по формуле:

где i = 3, j =1, k 3, p 1.

Формулу эту называют «правилом прямоугольника», ибо ее легко запомнить, пользуясь прямоугольником:

Правило для запоминания формулы: для получения новой вершины а ' прямоугольника надо из старой вершины а вычесть произведение a а двух взаимно противоположных других вершин прямоугольника, деленное на вершину a , противоположную старой вершине а .

В результате получаем следующую таблицу 3:

Таблица 3

Б.п	х1	х2	х3	х4	х5	С.к
х3					–5
х4
х1		–1
f		–7

Снова выбираем разрешающий столбец по максимуму модуля отрицательного индекса, им будет второй столбец.

Так как min , то первая строка будет разрешающей.

Переменную х ₂ вводим в состав базисных вместо х₃. Элементы первой строки делим на разрешающий элемент а₁₂ = 7. Элементы второго столбца, кроме а₁₂, заменяем нулями. Все остальные элементы таблицы 2 преобразуем по «правилу прямоугольника». Получим в результате таблицу 4.

---

Дата добавления: 2015-07-26