Решение задачи линейного программирования алгебраическим симплекс-методом

 

Применение алгебраического метода решения задачи требует обобщения представления задачи ЛП. Исходную систему ограничений, заданную в виде неравенств преобразуют к стандартной форме записи, когда ограничения заданы в виде равенств. Преобразование системы ограничений к стандартному виду включает в себя следующие этапы:

 

1.1 Преобразовать неравенства таким образом, чтобы слева находились переменные и свободные члены, а справа - 0 т.е. чтобы левая часть была больше или равной нулю;

1.2 Ввести дополнительные переменные, число которых равно числу неравенств в системе ограничений;

1.3 Введя дополнительные ограничения на неотрицательность добавленных переменных, заменить знаки неравенств на знаки строгих равенств.

 

При решении задачи ЛП алгебраическим методом добавляется условие: целевая функция должна стремиться к минимуму. Если данное условие не выполняется, необходимо соответствующим образом преобразовать целевую функцию (умножить на -1) и решать задачу минимизации. После того, как решение найдено, подставить значения переменных в исходную функцию и посчитать ее значение.

Решение задачи при использовании алгебраического метода считается оптимальным, когда значения всех, базисных переменных – неотрицательно, и коэффициенты при свободных переменных в уравнении целевой функции также неотрицательны. Если эти условия не выполняются, необходимо преобразовать систему неравенств, выражая одни переменные через другие (меняя свободные и базисные переменные) добиться выполнения вышеприведенных ограничений. Значение всех свободных переменных считается равным нулю.

Алгебраический метод решения задач линейного программирования является одним из самых эффективных методов при решении задач небольшой размерности вручную т.к. не требует большого числа арифметических вычислений. Машинная реализация этого метода сложнее, чем, например, для симплекс-метода, т.к. алгоритм решения алгебраическим методом является в какой то степени эвристическим и эффективность решения во многом зависит от личного опыта.

 

 

- свободных переменных

 

Шаг 1.

св.пер. - доп. набор

 

Из (2)

Анализ

 

Шаг 2.

св. пер.

 

 

Анализ

 

Шаг 3.

 

св. пер.

 

 

 

Условия не отрицательности выполнены, следовательно, найдено оптимальное решение.

 

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

Симплекс-таблицы.

 

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

 

Все уравнения системы приведем к виду:

 

Строим симплекс-таблицу:

- В верхний угол каждой клетки таблицы вписываем коэффициенты из системы уравнений;

- Выбираем максимальный положительный элемент в строке F, кроме b, это будет генеральный столбец;

- Для того, чтобы найти генеральный элемент строим отношение для всех положительных a. 3/3; 9/1;- минимальное соотношение в строке x3. Следовательно - генеральная строка и a=3 - генеральный элемент.

- Находим l=1/a=1/3. Вносим l в нижний угол клетки, где находится генеральный элемент;

- Во все незаполненные нижние углы генеральной строки вносим произведение значения в верхнем углу клетки на l;

- Выделяем верхние углы генеральной строки;

- Во все нижние углы генерального столбца заносим произведение значения в верхнем углу на -l и выделяем полученные значения;

- Остальные клетки таблицы заполняются, как произведения соответствующих выделенных элементов;

- Затем строим новую таблицу, в которой обозначения клеток элементов генерального столбца и строки меняются местами (x2 и x3);

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

- В верхний угол остальных клеток записывается сумма значений верхнего и нижнего угла этих клеток в предыдущей таблице

 

 

Свободные   Базисные
		-2 -2/3	1/3
	-1	2/3	-1/3
		-2/3	-1 1/3
		-2/3	-1 1/3
	-5	-1   10/3	-5/3

 

 

 

Свободные   Базисные
		-2/3 1/4	1/3   -1/12
		8/3 3/8	-1/3 -1/8
	-1	1/3 -1/8	1/3   1/24
	-1	1/3 -1/8	1/3   1/24
	-5 -7	7/3 -7/8	-5/3   7/24

 

 

Свободные   Базисные
		1/4	1/4
		3/8	-1/8
		-1/8	9/24
		-1/8	9/24
	-12	-7/8	-11/8

 

 

 

Анализируя полученные результаты, можно сделать вывод, что найдено оптимальное решение задачи линейного программирования:

 

Х1 = 3, Х2 = 3, Fmin = -12