Для данной задачи линейного программирования:
построить ее математическую модель;
решить ее геометрическим методом;
решить ее симплекс-методом;
построить задачу, двойственную к данной и найти её решение;
дать экономическую интерпретацию полученным ответам.
Для производства двух видов продукции (А и В) предприятие должно использовать оборудование трех видов (I, II, III), имеющиеся в количествах соответственно 8, 6, 9 ед. По техническим условиям для производства 1 шт. продукции А требуется 2 ед. оборудования I вида, 1 ед. оборудования II вида и 3 ед. оборудования III вида, для производства 1 шт. продукции В – 2, 2 и 0 ед. соответствующих видов оборудования. Известно, что от реализации 1 шт. продукции А предприятие получит 1 ден. ед. прибыли, 1 шт. продукции В – 3 ден. ед. Сколько единиц продукции каждого вида должно выпустить предприятие, чтобы получить наибольшую прибыль.
Ответ
необходимо выпускать только продукцию вида В в количестве 3 единицы, чтобы получить максимальную прибыль в размере 9 ден ед
Решение
1)Построим математическую модель задачи.
Пусть х1-количество изделий вида А, ед, х2 - количество изделий вида В, ед запланированных к производству. Для их изготовления потребуется (2 х1 +2х2) единиц ресурса I, (х1 +2х2) единиц ресурса II, (3х1 ) единиц ресурса III. Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
2x1+2х2≤8x1+2х2≤63x1≤9
По смыслу задачи переменные х1 ≥ 0, х2 ≥0.
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.
Суммарная прибыль составит х1 от реализации продукции А и 3х 2 от реализации продукции В, то есть : F = х1 +3х 2. →max.
2)Построим область допустимых решений, т.е. решим графически систему неравенств.
Границей неравенства x1+x2≤4 является прямая x1+x2=4, построим ее по двум точкам:
х1
0 4
х2
4 0
Произвольная точка (0; 0) удовлетворяет неравенству x1+x2≤4, поэтому областью решения неравенства будут точки, лежащие ниже прямой x1+x2=4. Область решения обозначим штриховкой.
Границей неравенства x1+2x2≤6 является прямая x1+2x2=6 , построим ее по двум точкам:
х1
0 6
х2
3 0
Произвольная точка (0; 0) удовлетворяет неравенству x1+2x2≤6 , поэтому областью решения неравенства будут точки, лежащие ниже прямой x1+2x2=6 . Объединим полученную полуплоскость с ранее найденными ограничениями и с ограничением x1≤3 . Область решения обозначим штриховкой.
Общая часть всех полуплоскостей область АВСDE является областью решений системы линейных неравенств.
Строим вектор-градиент целевой функции FX=x1+3x2:
∇F=1;3.
(координаты вектора-градиента – частные производные функции ).
Проводим линию линейной функции перпендикулярно вектору-градиенту
.
Для отыскания точки, соответствующей максимальному значению функции, сдвигаем линию уровня параллельно самой себе в направлении, указанном вектором ∇F.
Максимального значения функция достигает в точке: F(В),В(0,3)
Fmax=FВ=1∙0+3*3=9.
3)Решим задачу симплекс методом
Избавимся от неравенств в ограничениях, введя балансовые переменные:
x1+х2+х3=4x1+2х2+х4=6x1+х5=3
В полученной системе ограничений базисными переменными являются x4, x5, x3.
Формируем начальную симплекс-таблицу:
Базисные переменные х1
х2
х3 х4
х5 Свободные члены
Х3 1 1 1 0 0 4
Х4
1 2 0 1 0 6
Х5 1 0 0 0 1 3
F -1 -3 0 0 0
За ведущий выберем столбец 2, так как -3 наименьший элемент в F строке. За ведущую выберем строку 2, так как отношение свободного члена к соответствующему элементу выбранного столбца для второй строки является наименьшим.
Базисные переменные х1
х2
х3 х4
х5 Свободные члены отношение
Х3 1 1 1 0 0 4 4
Х4
1 2 0 1 0 6 3
Х5 1 0 0 0 1 3 -
F -1 -3 0 0 0
Элементы разрешающей строки делим на разрешающий элемент и записываем в соответствующей по номеру строке новой таблицы: , при i = r.Все остальные элементы новой таблицы рассчитываем по формулам:
,при i ≠ r
где - элемент новой симплекс-таблицы, aij, - элемент предыдущей симплекс-таблицы, ark - разрешающий элемент , aik - элемент разрешающего столбца, arj - элемент разрешающей строки.
Базисные переменные х1
х2
х3 х4
х5 Свободные члены
Х3 ½ 0 1 -1/2 0 1
Х2
½ 1 0 1/2 0 3
Х5 1 0 0 0 1 3
F 1/2 0 0 3/2 0 9
В строке F нет отрицательных элементов, значит, полученный план оптимален.
Оптимальный план:
x1=0, x2=3, F=9.
В оптимальный план вошла дополнительная переменная x3, X5 Следовательно, при реализации такого плана имеются недоиспользованные ресурсы первого и третьего сорта в количестве 1ед и 3 ед
Задать вопрос
на новый заказ в Автор24.
