При изготовлении изделий A и B используется три вида сырья. На производство единицы изделия A требуется затратить 6 кг сырья первого вида, 5 кг второго и 3 кг третьего. На производство единицы изделия B расходуется соответственно 3 кг, 10 кг и 12 кг. Запас сырья первого вида 714 кг, второго – 910 кг, третьего – 948 кг. Прибыль от реализации готового изделия A составляет 3 руб., изделия B – 9 руб. Составить план производства изделий A и B, максимизирующий прибыль.
Дополнительное условие: должно быть выпущено не менее 80 единиц изделия A.
Решение:
Пусть x1 и x2 – количество изделий A и B. Из условий задачи получаем, что прибыль от реализации готовых изделий A составляет 3×1 руб., а изделий B – 9×2 руб. Прибыль от реализации F можно выразить формулой:
F=3×1+9×2
Поскольку требуется получить максимальную прибыль, целевая функция примет вид:
F=3×1+9×2 →max
Так как переменные x1, x2 выражают количество единиц контейнеров, то фактически они не могут быть отрицательными:
x1≥0,×2≥0
На производство изделий A затрачивает 6×1 кг сырья первого вида, а на производство изделия B – 3×2 кг, тогда общая сумма затрат сырья первого вида составит 6×1+3×2 кг. Поскольку запас ресурса ограничен и составляет 714 кг, получаем ограничение:
6×1+3×2≤714
Аналогично получаем ограничения для сырья второго и третьего видов:
5×1+10×2≤910
3×1+12×2≤948
В результате получаем математическую модель задачи:
F=3×1+9×2 →max
6×1+3×2≤7145×1+10×2≤9103×1+12×2≤948
x1≥0,×2≥0
Приведем задачу к каноническому виду, введя переменные s1, s2 и s3, которые представляют собой неиспользованный ресурс:
F=3×1+9×2 →max
6×1+3×2+s1=7145×1+10×2+s2=9103×1+12×2+s3=948
x1≥0,×2≥0,s1≥0,s2≥0,s3≥0.
Решить задачу симплекс-методом.
Составим первую симплекс-таблицу:
Базис Cбаз
B
3 9 0 0 0
x1
x2
s1
s2
s3
s1
0 714 6 3 1 0 0
s2
0 910 5 10 0 1 0
s3
0 948 3 12 0 0 1
Оценки F=0
–3 –9 0 0 0
В последней строке оценок присутствуют отрицательные оценки, следовательно, план не оптимален.
Найдем отношение координат вектора B к соответствующим, но только положительным координатам вектора x2 (столбец с максимальной по модулю отрицательной оценкой) и выберем минимальное из них:
min7143;91010;94812=min238;91;79=79
Из этого следует, что из базиса надо вывести s3 и ввести x2.
Переходим к нахождению нового опорного решения, для чего составляем новую симплекс таблицу с новым базисом s1, s2, x2.
Заполнение новой симплекс таблицы начинаем с заполнения строки, соответствующей вновь вводимому вектору x2. Она получается делением элементов ведущей строки на ведущий элемент. Остальные элементы таблицы можно найти исходя из формулы:
xij’=xij-xis∙xsjxsr,
где xij’ – искомый элемент в новой таблице; xsr – ведущий элемент; xis – элемент, стоящий в проекции элемента xij на ведущий столбец; xsj – элемент, стоящий в проекции xij на ведущую строку.
Получаем новую симплекс таблицу:
Базис Cбаз
B
3 9 0 0 0
x1
x2
s1
s2
s3
s1
0 477 5,25 0 1 0 –0,25
s2
0 120 2,5 0 0 1 –0,083
x2
9 79 0,25 1 0 0 0,083
Оценки F=711
–0,75 0 0 0 0,75
В последней строке оценок присутствуют отрицательные оценки, следовательно, план не оптимален.
Найдем отношение координат вектора B к соответствующим положительным координатам вектора x1 и выберем минимальное из них:
min4775,25;1202,5;790,25=min90,857;48;316=48
Из этого следует, что из базиса надо вывести s2 и ввести x1.
Переходим к нахождению нового опорного решения, для чего составляем новую симплекс таблицу с новым базисом s1, x1, x2. Переходим к новой симплекс-таблице:
Базис Cбаз
B
3 9 0 0 0
x1
x2
s1
s2
s3
s1
0 225 0 0 1 –2,1 1,5
x1
3 48 1 0 0 0,4 –0,333
x2
9 67 0 1 0 –0,1 0,167
Оценки F=747
0 0 0 0,3 0,5
В последней строке нет отрицательных оценок, следовательно, полученный план оптимален. При этом x1=48, x2=67, s1=225, s2=0, s3=0, F=747.
Таким образом, по данным последней симплекс-таблицы следует производить 48 ед. изделий A и 67 ед. изделий B, тогда прибыль будет максимальной и составит 747 руб. При этом сырье второго и третьего видов расходуется полностью, т.к. s2=0 и s3=0, а сырья первого вида останется в размере 225 кг.
Двойственные оценки в индексной строке характеризуют прирост прибыли на единицу прироста соответствующего ресурса.
Согласно последней симплекс-таблице получаем двойственные оценки:
y1=0, y2=0,3, y3=0,5.
Таким образом, ресурсы третьего вида наиболее эффективны для производства. Каждая единица прироста этого ресурса обеспечивает увеличение целевой функции на 0,5 руб., прирост сырья второго вида – на 0,3 руб., а сырье первого вида не является дефицитным, поэтому дополнительные единицы сырья первого вида для увеличения объемов оптимального плана не требуются.
Таким образом, если запас сырья второго увеличатся на 10 кг, то прибыль составит:
F=747+10∙0,3=750 кг,
а если запас сырья третьего увеличатся на 10 кг, то прибыль составит:
F=747+10∙0,5=752 кг.
Решим задачу графическим способом.
Так как x1≥0 и x2≥0, то область допустимых решений будет лежать первой координатной четверти.
На первой координатной четверти строим прямые, порождаемые системой ограничений. Для построения прямых заменяем знаки неравенства в системе ограничений на знаки равенства.
l1:6×1+3×2=714l2:5×1+10×2=910l3:3×1+12×2=948 ⇔ l1:2×1+x2=238l2:x1+2×2=182l3:x1+4×2=316
Относительной каждой прямой определяем полуплоскость, соответствующую исходным неравенствам. Область допустимых решений (ОДР) лежит ниже прямых.
Построим также вектор градиента n=(3;9). Для этого соединим начало координат с точкой (9;27).Перпендикулярно к нему построим одну из семейства прямых F=3×1+9×2=const. Например, при F=450.
Вспомогательную прямую F=450, будем перемещать в направлении вектора n (так как нам надо найти максимум) до последней точки пересечения с областью допустимых решений. Прямая F выходит из ОДР в точке B, которая находится на пересечении прямых l2 и l3:
x1+2×2=182×1+4×2=316
Решая систему, получаем x1=48 и x2=67, тогда:
Fmax=F48;67=3∙48+9∙67=747
Таким образом, следует производить 48 ед. изделий A и 67 ед. изделий B, тогда прибыль будет максимальной и составит 747 руб.
При изменении коэффициентов целевой функции F=c1x1+c2x2 точка B останется точкой оптимального решения до тех пор, пока угол наклона линии F будет лежать между углами наклона прямых l2 (x1+2×2=182) и l3 (x1+4×2=316). Алгебраически это можно записать следующим образом:
21≤c2c1≤41, c1≠0
14≤c1c2≤12, c2≠0
В первой системе неравенств условие c1≠0 означает, что прямая, соответствующая целевой функции, не может быть горизонтальной. Аналогичное условие в следующей системе неравенств означает, что эта же прямая не может быть вертикальной.
Из графического решения видно, что интервал оптимальности данной задачи не разрешает целевой функции быть ни горизонтальной, ни вертикальной прямой. Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности в нашем примере.
Итак, если коэффициенты c1 и c2 удовлетворяют приведенным выше неравенствам, оптимальное решение будет достигаться в точке B.
Отметим, если прямая F=c1x1+c2x2 совпадет с прямой l2, то оптимальным решением будет любая точка отрезка BC. Аналогично, если прямая, соответствующая целевой функции, совпадет с прямой l3, тогда любая точка отрезка AB будет оптимальным решением. Однако заметим, что в обоих случаях точка B остается точкой оптимального решения.
Подставляя c2=9, получаем:
94≤c1 ≤92,
а подставляя c1=3, получаем:
6≤с2≤12
Таким образом, решение будет оптимальным при изменении цены изделия A от 2,25 до 4,5 руб., а изделия B – от 6 до 12 руб.
Если предприятия полагает, что должно быть выпущено не менее 80 изделий A, математическая модель задач примет вид:
F=3×1+9×2 →max
6×1+3×2≤7145×1+10×2≤9103×1+12×2≤948×1≥80
x1≥0,×2≥0
Решим задачу графически, проведя дополнительную прямую l1: x1=80. Получаем график:
Вспомогательную прямую F=450, будем перемещать в направлении вектора n до последней точки пересечения с областью допустимых решений. Прямая F выходит из ОДР в точке B, которая находится на пересечении прямых l2 и l4:
x1+2×2=182×1=80
Решая систему, получаем x1=80 и x2=51, тогда:
Fmax=F80;51=3∙80+9∙51=699
Таким образом, следует производить 80 ед. изделий A и 51 ед. изделий B, тогда прибыль будет максимальной и составит 699 руб.
Решим задачу симплекс-методом. Для этого приведем новую задачу к каноническому виду:
F=3×1+9×2 →max
6×1+3×2+s1=7145×1+10×2+s2=9103×1+12×2+s3=948-x1+s4=-80
x1≥0,×2≥0,s1≥0,s2≥0,s3≥0,s4≥0.
Составим первую симплекс-таблицу:
Базис Cбаз
B
3 9 0 0 0 0
x1
x2
s1
s2
s3
s4
s1
0 714 6 3 1 0 0 0
s2
0 910 5 10 0 1 0 0
s3
0 948 3 12 0 0 1 0
s4
0 –80 –1 0 0 0 0 1
Оценки F=0
–3 –9 0 0 0 0
Данный план не допустим, т.к. вектор B содержит отрицательные оценки.
Найдем отношение координат строки оценок к соответствующим, но только отрицательным координатам строки s4 (строка с максимальной по модулю величине с отрицательной оценкой в столбце B) знаком и выберем минимальное из них:
min-3-1;-;-;-;-;-=3
Из этого следует, что из базиса надо вывести s4 и ввести x1.
Переходим к нахождению нового опорного решения, для чего составляем новую симплекс таблицу с новым базисом s1, s2, s3, x1. Переходим к новой симплекс-таблице:
Базис Cбаз
B
3 9 0 0 0 0
x1
x2
s1
s2
s3
s4
s1
0 234 0 3 1 0 0 6
s2
0 510 0 10 0 1 0 5
s3
0 708 0 12 0 0 1 3
x1
3 80 1 0 0 0 0 –1
Оценки F=240
0 –9 0 0 0 –3
В последней строке оценок присутствуют отрицательные оценки, следовательно, план не оптимален.
Найдем отношение координат вектора B к соответствующим положительным координатам вектора x2 и выберем минимальное из них:
min2343;51010;70812;-=min78;51;59;-=51
Из этого следует, что из базиса надо вывести s2 и ввести x2.
Переходим к нахождению нового опорного решения, для чего составляем новую симплекс таблицу с новым базисом s1, x2, s3, x1. Переходим к новой симплекс-таблице:
Базис Cбаз
B
3 9 0 0 0 0
x1
x2
s1
s2
s3
s4
s1
0 81 0 0 1 –0,3 0 4,5
x2
9 51 0 1 0 0,1 0 0,5
s3
0 96 0 0 0 –1,2 1 –3
x1
3 80 1 0 0 0 0 –1
Оценки F=699
0 0 0 0,9 0 1,5
В последней строке нет отрицательных оценок, следовательно, полученный план оптимален. При этом x1=80, x2=51, s1=81, s2=0, s3=96, s4=0, F=699.
Таким образом, по данным последней симплекс-таблицы следует производить 80 ед. изделий A и 51 ед. изделий B, тогда прибыль будет максимальной и составит 699 руб. При этом сырье второго вида расходуется полностью, т.к. s2=0, план по производству изделия A выполняется на 100%, а сырья первого и третьего видов останется в размере 81 и 96 кг.
