Симплексный метод и его геометрическая интерпретация

Математическая модель задачи
Переменные задачи:
x1 – количество продукции А, ед.;
x2 – количество продукции В, ед.;
x3 – количество продукции С, ед.
Тогда:
3x1+5x2 – затраченное сырье первого вида, ед.;
x1+x2+x3 – затраченное сырье второго вида, ед.;
2x2 – затраченное сырье третьего вида, ед.
Ограничения:
Запасы сырья первого вида равны 30 ед., второго вида – 8 ед., третьего вида – 8 ед. Сырье второго вида должно быть израсходовано полностью. Значит, должны выполняться следующие соотношения:
3x1+5x2 ≤30(1)
x1+x2+x3=8(2)
2x2≤8(3)
По смыслу задачи переменные должны быть неотрицательными числами:
xi≥0, i=1,3(4)
Целевая функция:
Прибыль от реализации единицы продукции А составляет 3 ден. ед., продукции В – 3 ден. ед., продукции С – 1 ден. ед. Тогда общая прибыль равна:
F=3x1+3x2+x3(5)
Таким образом, получена математическая модель задачи:
Найти максимальное значение функции F=3x1+3x2+x3→max при условиях:
3x1+5x2 ≤30x1+x2+x3=82x2≤8xi≥0, i=1,3
Приведение задачи к канонической форме
Запишем задачу в форме основной задачи линейного программирования. В системе ограничений перейдем от неравенств к равенствам, для чего введем дополнительные переменные x4, x5 ≥0.
Система ограничений примет вид:
3x1+5x2+x4=30x1+x2+x3=82x2+x5=8xi≥0, i=1,5
Целевая функция примет вид:
FX=3x1+3x2+x3+0∙x4+0∙x5→max
Решение задачи симплекс-методом
Преобразованную систему ограничений можно записать в векторной форме:
x1Р1+x2Р2+x3Р3+x4Р4+x5Р5=Р0, где
Р1=310, Р2=512, Р3=010, Р4=100, Р5=001, Р0=3088
Для основной задачи можно записать опорный план X1=(0;0;8;30;8), который определяется системой единичных векторов Р3, Р4, Р5 (они образуют базис трехмерного пространства).
Переменныеx4,x3, x5 - базисные
Составим первую симплекс-таблицу.
Таблица 1
№ Базис Сб
Р0
Переменные

3 3 1 0 0
1 x4
0 30 3 5 0 1 0
2 x3
1 8 1 1 1 0 0
3 x5
0 8 0 2 0 0 1
F=8 –2 –2 0 0 0
Опорный план: X1=(0;0;8;30;8).
F=3∙0+3∙0+1∙8=8
Найдем оценки:
∆j=i=13ciaij-cj
где cj – коэффициенты при неизвестных целевой функции,
aij – коэффициенты при неизвестных в системе ограничений, ci – коэффициенты при базисных переменных.
Оценки в столбцах базисных переменных равны 0: ∆3=∆4=∆5=0.
∆1=0∙3+1∙1+0∙0-3=-2
∆2=0∙5+1∙1+0∙2-3=-2
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным. Среди коэффициентов при переменных в соответствующих столбцах есть положительные, поэтому можно перейти к новому базису и другому опорному плану.
В качестве переменной, вводимой в базис, возьмем переменную x1. Столбец переменной x1 – ключевой.
Для определения переменной, подлежащей исключению из базиса, составим отношения элементов столбца Р0 к соответствующим положительным значениям ключевого столбца и найдем среди них минимальное:
min303; 81=81
Значит, из базиса выводим переменную x3 . Вторая строка – ключевая, a21=1 – разрешающий элемент.
Перейдем ко второй симплекс-таблице.
Таблица 2
№ Базис Сб
Р0
Переменные

3 3 1 0 0
1 x4
0 6 0 2 -3 1 0
2 x1
3 8 1 1 1 0 0
3 x5
0 8 0 2 0 0 1
F=24 0 0 2 0 0
Заполнение второй симплекс-таблицы:
В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных проставляются 1, а остальные элементы этих столбцов равны 0.
Элементы столбцов Р0 и в строке переменной, вводимой в базис, получаем делением соответствующих элементов исходной таблицы на разрешающий элемент (на 1).
Остальные элементы столбцов Р0 и находим по правилу треугольника. Для вычисления какого-либо из этих элементов берем 3 числа:
число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;
число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего переменной, вводимой в базис;
число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и ключевой строки.
Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго и третьего.
столбец Р0 30-3∙8=6
8-0∙8=8
Х2 5-3∙1=2
2-0∙1=2
Х3 0-3∙1=-3
0-0∙1=0
Опорный план: X2=(8;0;0;6;8).
F=3∙8+3∙0+1∙0=24
Найдем оценки:
Оценки в столбцах базисных переменных равны 0: ∆1=∆4=∆5=0.
∆2=0∙2+3∙1+0∙2-3=0
∆3=0∙(-3)+3∙1+0∙0-1=2
Поскольку среди нет отрицательных оценок, то опорный планX2=(8;0;0;6;8) является оптимальным, Fmax=24
Учитывая переменные исходной задачи, получим, что оптимальный план исходной задачи равен X*=(8;0;0). Значение целевой функции максимально и равно Fmax=24.
Т.е., максимальная прибыль, равная 24 ден. ед., будет обеспечена при производстве 8 ед. продукции А.
Среди есть нулевая оценка в столбце переменной x2, не входящей в базис, значит, найденное решение не единственное. Еще одно решение можно получить, введя в базис переменную с нулевой оценкой.
Введем в базис переменную x2.
Столбец переменной x2 – ключевой.
Для определения переменной, подлежащей исключению из базиса, составим отношения элементов столбца Р0 к соответствующим положительным значениям ключевого столбца и найдем среди них минимальное:
min62; 81;82=62
Значит, из базиса выводим переменную x4. Первая строка – ключевая, a12=2 – разрешающий элемент.
Перейдем к третьей симплекс-таблице.
Таблица 3
№ Базис Сб
Р0
Переменные

3 3 1 0 0
1 x2
3 3 0 1 -1,5 0,5 0
2 x1
3 5 1 0 2,5 -0,5 0
3 x5
0 2 0 0 3 -1 1
F=24 0 0 2 0 0
Заполнение второй симплекс-таблицы:
В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных проставляются 1, а остальные элементы этих столбцов равны 0.
Элементы столбцов Р0 и в строке переменной, вводимой в базис, получаем делением соответствующих элементов исходной таблицы на разрешающий элемент (на 2).
Остальные элементы столбцов Р0 и находим по правилу треугольника