Для производства трех видов продукции A,B,C используется три вида сырья S1,S2,S3. Нормы затрат каждого из видов сырья на единицу продукции каждого вида и прибыль с единицы продукции приведены в таблице. Требуется определить план выпуска продукции, обеспечивающий предприятию максимальную прибыль при условии, что сырье S3 должно быть полностью израсходовано.
Виды сырья Продукция Запасы
А В С
S1 8 6 1 64
S2 12 4 1 64
S3 4 2 1 24
Прибыль 2 3 1
Решение:
Составим экономико-математическую модель:
Пусть x1 – количество единиц продукции А, шт.
х2 – количество единиц продукции В, шт.
х3 – количество единиц продукции С, шт.
Учитывается что прибыль от первого вида изделия составляет 2 д.ед, прибыль от второго вида – 3д.ед. и прибыли от третьего вида – 1д.ед. Тогда совокупный суточный доход составит:
F(x) = 2×1+3×2+x3→max
Помимо целевой функции, которая позволяет максимизировать доход от продажи продукции, наша задача имеет ряд ограничений:
Использование первого вида сырья (S1) при производстве изделий, с учетом максимально возможного суточного запаса продукции, запишется в виде ограничения:
8×1+6×2+x3≤64
Аналогично, использование второго вида сырья (S2) при производстве изделий, с учетом максимально возможного суточного запаса продукции, запишется в виде ограничения:
12×1+4×2+x3≤64
Использование третьего вида сырья (S3) при производстве изделий, с учетом максимально возможного суточного запаса продукции, запишется в виде ограничения:
4×1+2×2+x3=24
Т.к нам необходимо, чтобы сырье третьего вида было израсходовано полностью.
Поскольку объемы производства изделий X1, X2, X3 не могут быть отрицательными, исходя из экономического смысла задачи, необходимо ввести в модель условия неотрицательности:
x1≥0,×2≥0, x3≥0
Окончательный вид экономико-математической модели имеет вид:
F(x) = 2×1+3×2+x3→max (1)
8×1+6×2+x3≤6412×1+4×2+x3≤644×1+2×2+x3=24×1,x2,x3≥0 (2)
Таким образом, модель состоит из целевой функции, ограничений и условий неотрицательности.
Экономико-математическая модель задачи: Найти такой план выпуска продукции удовлетворяющий системе ограничений (2), при котором целевая функция (1) принимает максимальное значение.
Стандартная форма задачи:
F(x) = 2×1+3×2+x3→max
8×1+6×2+x3≤6412×1+4×2+x3≤644×1+2×2+x3=24×1,x2,x3≥0
Решим задачу графическим методом:
Базисные переменные системы ограничений и целевую функцию выразим через свободную переменную x1.
x1=8-34×2-18x3x1=163-13×2-112x3x1=6-12×2-14x3x1,x2,x3≥0
F(x) = 2×1+3×2+x3=2*6-12×2-14×3=12+2×2+12×3
Приведем к неравенствам и получим:
F(x) = 12+2×2+12×3
34×2+18×3≤8 (1)13×2+112×3≤163 (2)12×2+14×3=6 (3)x1,x2,x3≥0
Решим графическим способом:
34×2+18×3≤8 (L1) 2) 13×2+112×3≤163 (L2)
34×2+18×3=8 13×2+112×3=163
x2
10,6(6) 0
x3
0 64
x2
16 0
x3
0 64
12×2+14×3=6 L3
0.5×2+0.25×3=6
x2
12 0
x3
0 24
Вектор – градиент: GradF(x) = (2; 13).
Построим график и отметим на нем область ограничений и вектор градиент.
82309312636400
Т.к. у нас очень маленькое значение вектора градиента, то для наглядности, умножим каждое значение на 10. Но при подсчете функции, учитываем прежние значения.
Область решений: Прямая АВ.
т.max – является т. B. Найдем координаты точки B:
В т. В пересекаются 2 прямые: (L1 и L3)
34×2+18×3=812×2+14×3=6|*12; -34×2+18×3=814×2+18×3=3 ; x2=10;x3=4.
Fmax(x) = 12+2*10+12*4=34
Проведем анализ чувствительности
Концевые точки отрезка определяют интервал осуществимости для ресурса S1.Количество сырья, соответствующего точке (12,0), равно 0.75·12 + 0.125·0 = 9Количество сырья, соответствующего точке (0,24), равно 0.75·0 + 0.125·24 = 3
Таким образом, интервал осуществимости для ресурса M1 составляет 3 ≤ S1 ≤ 9Вычислим значение целевой функции в этих точках:F(12,0) = 2·12 + 0.5·0 = 24F(0,24) = 2·0 + 0.5·24 = 12
YS1 = 24-129-3 = 2
Произойдет изменение области решений при увеличении запасов ресурса S1
Концевые точки отрезка определяют интервал осуществимости для ресурса S3.Количество сырья, соответствующего точке (0,64), равно 0.5·0 + 0.25·64 = 16Количество сырья, соответствующего точке (10.67,0), равно 0.5·10.67 + 0.25·0 = 5.33
Таким образом, интервал осуществимости для ресурса M3 составляет 5.33 ≤ S3 ≤ 16Вычислим значение целевой функции в этих точках:F(0,64) = 2·0 + 0.5·64 = 32F(10.67,0) = 2·10.67 + 0.5·0 = 21.33
YS3 = 32-21.3316-5.33 = 1
На рисунке видно, что функция достигает своего оптимума в точке, которая является пересечением прямых (34×2+18×3=8) и (12×2+14×3=6). При изменении коэффициентов целевой функции эта точка останется точкой оптимального решения до тех пор, пока угол наклона линии z будет лежать между углами наклона этих прямых. Алгебраически это можно записать следующим образом:
0.1250.75 ≤ C2C1 ≤ 0.250.5
при условии c1 ≠ 0или
0.50.25 ≤ C1C2 ≤ 0.750.125 при условии c2 ≠ 0
Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности.При c2 = 0.5 При c1 = 2
0.50.25 ≤ C10.5 ≤ 0.750.125 0.1250.75 ≤ C22 ≤ 0.250.5или или1 ≤ c1 ≤ 3 0.33 ≤ c2 ≤ 1
Приведем задачу к канонической форме:
F(x) = 2×1+3×2+x3→max
8×1+6×2+x3≤6412×1+4×2+x3≤644×1+2×2+x3=24×1,x2,x3≥0 → 8×1+6×2+x3+x4=6412×1+4×2+x3+x5=644×1+2×2+x3=24xi≥0,(i=1,5)
Решим задачу симплекс-методом:
8×1+6×2+x3+x4=6412×1+4×2+x3+x5=644×1+2×2+x3=24xi≥0,(i=1,5)
Воспользуемся формой решения симплекс-метода – методом искусственного базиса.
Введем искусственные переменные x: в 3-м равенстве вводим переменную x6; 8×1+6×2+x3+x4=6412×1+4×2+x3+x5=64
4×1+2×2+x3=24Для постановки задачи на максимум целевую функцию запишем так:F(X) = 2×1+3×2+x3-Мx6 → max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М,т.е, это очень большое положительное число, которое обычно не задается.
Из уравнений выражаем искусственные переменные:x6= 24-4×1-2×2-x3 и подставим в целевую функцию:F(X) = 2×1+3×2+x3-М (24-4×1-2×2-x3)=(2+4M)x1+(3+2M)x2+(1+M)x3+(-24M) → max
Для наглядности составим симплекс-таблицу:
Базис Своб.пер. x1 x2 x3 x4 x5 x6 θ
x4 64 8 6 1 1 0 0 8
x5 64 12 4 1 0 1 0 6412
x6 24 4 2 1 0 0 1 6
F(X0) -24M -2-4M -3-2M -1-M 0 0 0
Θ находится как Своб.пер. делить на разрешающий столбец.
Составлен первый оптимальный план. Найдем разрешающий столбец, разрешающую строку и разрешающий элемент.
F(X0) = -24M; X0 = (0,0,0,64,64,24). План не оптимален, т.к. в строке F(X0) присутствуют отрицательные элементы. Выполним пересчет симплекс-таблицы.
Базис Своб.пер. x1 x2 x3 x4 x5 x6 θ
x4 64/3 0 10/3 1/3 1 -2/3 0 32/5
x1 16/3 1 1/3 1/12 0 1/12 0 16
x6 8/3 0 2/3 2/3 0 -1/3 1 4
F(X1) 102/3-22/3M 0 -21/3-2/3M -5/6-2/3M 0 1/6+M 0
Получим:
F(X1) = 102/3-22/3M ; X1 = (163,0,0, 643,0, 83). План не оптимален, т.к. в строке F(X1) присутствуют отрицательные элементы. Выполним пересчет симплекс-таблицы.
Базис Своб.пер. x1 x2 x3 x4 x5 x6 θ
x4 8 0 0 -3 1 1 -5 8
x1 4 1 0 -1/4 0 1/4 -1/2 16
x2 4 0 1 1 0 -1/2 3/2 -8
F(X2) 20 0 0 11/2 0 -1 31/2+M
F(X2) = 20; X2 = (4,4,0, 8,0, 0). План не оптимален, т.к. в строке F(X2) присутствуют отрицательные элементы. Выполним пересчет симплекс-таблицы.
Базис Своб.пер. x1 x2 x3 x4 x5 x6 θ
x5 8 0 0 -3 1 1 -5 -8/3
x1 2 1 0 1/2 -1/4 0 3/4 4
x2 8 0 1 -1/2 1/2 0 -1 -16
F(X3) 28 0 0 -11/2 1 0 -11/2+M
F(X3) = 28; X3 = (2,8,0, 0,8, 0). План не оптимален, т.к. в строке F(X3) присутствуют отрицательные элементы. Выполним пересчет симплекс-таблицы.
Базис Своб.пер. x1 x2 x3 x4 x5 x6
x5 20 6 0 0 -1/2 1 -1/2
x3 4 2 0 1 -1/2 0 3/2
x2 10 1 1 0 1/4 0 -1/4
F(X4) 34 3 0 0 1/4 0 3/4+M
F(X3) = 34; X3 = (0,10, 4, 0,20, 0). План оптимален, т.к в строке F(X4) нет отрицательных элементов.
Оптимальный план:
x1=0, x2=10, x3=4.
F(x) = 2*0 + 3*10 + 1*4 = 34.
Решим задачу на компьютере с использованием программы Microsoft Excel.
Формула в ячейке D9:
687574891000
Формула в ячейке E4: (Аналогичная формула и в ячейке E5)
15266510855600
Полученный результат:
23772610436100
74822226831000Ограничения:
Результаты в программе Microsoft Excel и при пересчете в ручную полностью совпали.
