Library

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

Определим максимальное значение целевой функции F(X) = 7x₁+3x₂ при следующих условиях-ограничений.

x₁+2x₂≤80

1.5x₁+x₂≤40

1x₁ + 2x₂ + 1x₃ + 0x₄ = 80

1.5x₁ + 1x₂ + 0x₃ + 1x₄ = 40

Решение задачи.

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x₃, x₄,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,80,40)

 

Базис	В	x1	x2	x3	x4
x3	80	1	2	1	0
x4	40	1.5	1	0	1
F(X0)	0	-7	-3	0	0

 

Переходим к основному алгоритму симплекс-метода.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

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

 

Базис	В	x1	x2	x3	x4	min
x3	80	1	2	1	0	80
x4	40	1.5	1	0	1	26.67
F(X1)	0	-7	-3	0	0	0

 

 

После преобразований получаем новую таблицу:

 

Базис	В	x1	x2	x3	x4
x3	53.33	0	1.33	1	-0.67
x1	26.67	1	0.67	0	0.67
F(X1)	186.67	0	1.67	0	4.67

 

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

 

Базис	В	x1	x2	x3	x4
x3	53.33	0	1.33	1	-0.67
x1	26.67	1	0.67	0	0.67
F(X2)	186.67	0	1.67	0	4.67

 

Оптимальный план можно записать так:

x₃ = 53.33

x₁ = 26.67

F(X) = 7*26.67 = 186.67