На кондитерскую фабрику перед Новым годом поступили заказы на подарочные наборы конфет из трех магазинов

Запишем условия задачи в виде модели задачи линейного программирования. Задачу можно сформулировать следующим образом: определим максимальное значение целевой функции:
FX=72x1+62x2+ 76x3→max.
При следующих ограничениях:
0,3x1+0,2x2+ 0,4x3≤6000,2x1+0,3x2+ 0,2x3≤7000,2x1+0,1x2+ 0,1x3≤500xj≥0, J=1,3
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных. В 1-м неравенстве вводим базисную переменную x4. В 2-м неравенстве вводим базисную переменную x5. В 3-м неравенстве вводим базисную переменную x6:
0,3x1+0,2x2+ 0,4x3+ x4=6000,2x1+0,3x2+ 0,2x3+x5=7000,2x1+0,1x2+ 0,1x3+x6=500xj≥0, J=1,6
Занесем данные в симплекс таблицу.
Таблица 2 – Базовый план
Базис bi 72 62 76 0 0 0 d = bi/aij
x1 x2 x3 x4 x5 x6
x4 600 0,3 0,2 0,4 1 0 0
x5 700 0,2 0,3 0,2 0 1 0
x6 500 0,2 0,1 0,1 0 0 1
m+1 0 -72 -62 -76 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю. Вычислим значения di по строкам и из них выберем наименьшее:
min (600 : 0,4 , 700 : 0,2 , 500 : 0,1 ) = 1500
Следовательно, 1-ая строка является ведущей.Разрешающий элемент равен 0,4 и находится на пересечении ведущего столбца и ведущей строки.
Таблица 3 – Симплекс таблица
Базис bi 72 62 76 0 0 0 d = bi/aij
x1 x2 x3 x4 x5 x6
x4 600 0,3 0,2 0,4 1 0 0 1500
x5 700 0,2 0,3 0,2 0 1 0 3500
x6 500 0,2 0,1 0,1 0 0 1 5000
m+1 0 -72 -62 -76 0 0 0
Формируем следующую часть симплексной таблицы . Вместо переменной x4 в план 1 войдет переменная x3.Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ = 0,4. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Таким образом, в новом плане 1 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ, (1)
где СТЭ - элемент старого плана,
РЭ - разрешающий элемент,
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Получаем новую симплекс-таблицу.
Таблица 4 – План 1
Базис bi 72 62 76 0 0 0 d = bi/aij
x1 x2 x3 x4 x5 x6
х3 1500 0,75 0,5 1 2,5 0 0
x5 400 0,05 0,2 0 -0,5 1 0
x6 350 0,125 0,05 0 -0,25 0 1
m+1 114000 -15 -24 0 190 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения di по строкам и из них выберем наименьшее:
min (1500 : 0.5 , 400 : 0.2 , 350 : 0.05 ) = 2000.
Следовательно, 2-ая строка является ведущей.Разрешающий элемент равен (0,2) и находится на пересечении ведущего столбца и ведущей строки.
Таблица 5 – Симплекс таблица
Базис bi 72 62 76 0 0 0 d = bi/aij
x1 x2 x3 x4 x5 x6
х3 1500 0,75 0,5 1 2,5 0 0 3000
x5 400 0,05 0,2 0 -0,5 1 0 2000
x6 350 0,125 0,05 0 -0,25 0 1 7000
m+1 114000 -15 -24 0 190 0 0
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ = 0.2