Пусть необходимо выпустить изделий 1 – х1

Математическая модель задачи имеет вид:
F(X) = 8x1+7x2+6x3 → max
3x1+4x2+2x3≤780,x1+4x2+5x3≤850,2x1+3x2+4x3≤790,
х1>0,
х2>0,
х3>0.
Решим прямую задачу линейного программирования симплексным методом с использованием симплексной таблицы.
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
3x1+4x2+2x3+x4 = 780
x1+4x2+5x3+x5 = 850
2x1+3x2+4x3+x6 = 790
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A = 3 4 2 1 0 0
1 4 5 0 1 0
2 3 4 0 0 1
Базисные переменные – это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,0,780,850,790).
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6
x4 780 3 4 2 1 0 0
x5 850 1 4 5 0 1 0
x6 790 2 3 4 0 0 1
F(X0) 0 -8 -7 -6 0 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1↓ x2 x3 x4 x5 x6 min
←x4 780 3 4 2 1 0 0 260
x5 850 1 4 5 0 1 0 850
x6 790 2 3 4 0 0 1 395
∆ 0 -8 -7 -6 0 0 0
БП B x1 x2 x3↓ x4 x5 x6 min
x1 260 1 4/3 2/3 1/3 0 0 390
x5 590 0 8/3 13/3 -1/3 1 0 1770/13
←x6 270 0 1/3 8/3 -2/3 0 1 405/4
∆ 2080 0 11/3 -2/3 8/3 0 0
БП B x1 x2 x3 x4 x5 x6
x1 385/2 1 5/4 0 1/2 0 -1/4
x5 605/4 0 17/8 0 3/4 1 -13/8
x3 405/4 0 1/8 1 -1/4 0 3/8
∆ 4295/2 0 15/4 0 5/2 0 1/4
Среди значений индексной строки нет отрицательных