Для изготовления шоколада трех видов используется сырье трех видов.

Пример 1:

Для изготовления шоколада трех видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 252, 120 и 240 т. Количество сырья каждого вида, необходимое для производства единицы шоколада первого вида, соответственно равны: 4, 4 и 2 т. Для шоколада второго вида: 4, 4 и 12 т. Для шоколада третьего вида: 6, 4 и 12 т.  Прибыль от реализации единицы товары первого, второго и третьего вида соответственно равны: 10, 20 и 15 условных единиц. Найти ежедневный объем выпуска товаров каждого видов, при котором прибыль предприятия будет максимальной.

Решение от преподавателя:

F(X) = 10x₁+20x₂+15x₃ → max

при ограничениях: 
4x₁+4x₂+6x₃≤252 
4x₁+4x₂+4x₃≤120 
2x₁+12x₂+12x₃≤240 
x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0 

Расширенная матрица системы ограничений-равенств данной задачи: 

1. В качестве базовой переменной можно выбрать x₄. 
2. В качестве базовой переменной можно выбрать x₅. 
3. В качестве базовой переменной можно выбрать x₆. 
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6). 
Выразим базисные переменные через остальные: 
x₄ = -4x₁-4x₂-6x₃+252 
x₅ = -4x₁-4x₂-4x₃+120 
x₆ = -2x₁-12x₂-12x₃+240 
Подставим их в целевую функцию: 
F(X) = 10x₁+20x₂+15x₃ 
4x₁+4x₂+6x₃+x₄=252 
4x₁+4x₂+4x₃+x₅=120 
2x₁+12x₂+12x₃+x₆=240 
Решим систему уравнений относительно базисных переменных: x₄, x₅, x₆ 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X0 = (0,0,0,252,120,240) 

Переходим к основному алгоритму симплекс-метода. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 
и из них выберем наименьшее: 
min (252 : 4 , 120 : 4 , 240 : 12 ) = 20 
Следовательно, 3-ая строка является ведущей. 
Разрешающий элемент равен (12) и находится на пересечении ведущего столбца и ведущей строки. 

Формируем следующую часть симплексной таблицы. Вместо переменной x₆ в план 1 войдет переменная x₂. 
Получаем новую симплекс-таблицу: 

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 
и из них выберем наименьшее: 
min (172 : 3¹/₃ , 40 : 3¹/₃ , 20 : ¹/₆ ) = 12 
Следовательно, 2-ая строка является ведущей. 
Разрешающий элемент равен (3¹/₃) и находится на пересечении ведущего столбца и ведущей строки. 

Формируем следующую часть симплексной таблицы. Вместо переменной x₅ в план 2 войдет переменная x₁. 
Получаем новую симплекс-таблицу: 

Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план 
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. 
Окончательный вариант симплекс-таблицы: 

Оптимальный план можно записать так: 
x₁ = 12, x₂ = 18, x₃ = 0, x₄ = 132, x₅ = 0, x₆ = 0 
F(X) = 10•12 + 20•18 + 15•0 = 480