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

На кондитерскую фабрику перед Новым годом поступили заказы на подарочные наборы конфет из трех магазинов. Возможные варианты наборов, их стоимость и товарные запасы на фабрике представлены в таблице 1. Таблица 1 – Исходные данные Наименование конфет Вес конфет в наборе, кг Запасы конфет, кг А В С Сникерс 0,3 0,2 0,4 600 Марс 0,2 0,3 0,2 700 Баунти 0,2 0,1 0,1 500 Цена, руб. 72 62 76 Определить оптимальное соотношение количества подарочных наборов, которые фабрика может предложить магазинам и обеспечить максимальный доход от продажи.

Запишем условия задачи в виде модели задачи линейного программирования. Задачу можно сформулировать следующим образом: определим максимальное значение целевой функции:
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