Решить задачу линейного программирования
Предприятие выпускает два вида продукции I и II, для производства которых используется сырье трех видов. На изготовление единицы изделия I требуется затратить сырья каждого вида ai1 кг соответственно, а для единицы изделия II - ai2 кг. Нормативы затрат ресурсов на единицу продукции( общие для всех вариантов) приведены в таблице.
ресурсы Виды продукции Запасы ресурсов
I II
Р1 13 4 1990
Р2 6 5 3210
Р3 12 10 4210
Стоимость готовой продукции 8 9
Требуется составить план производства изделий I и II, обеспечивающий максимальную стоимость готовой продукции.
Решить задачу графически
Сформулируйте двойственную задау и найдите ее решение.
Определите интервалы устойчивости двойственных оценок по отношению к изменению сырья каждого вида в отдельности.
Решите задачу симплекс методом
Ответ
необходимо выпускать 421 ед изделий вида II, изделия вида I не выпускать, чтобы получить максимальную прибыль в размере 3789 ден ед
Решение
Построим математическую модель задачи.
Пусть х1-количество изделий вида I, ед, х2 - количество изделий вида II, ед запланированных к производству. Для их изготовления потребуется (13 х1 +4х2) единиц ресурса РI, (6х1 +5х2) единиц ресурса РII, (6х1 +5х2) единиц ресурса РIII. Так как, потребление ресурсов РI, РII, РIII не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
13x1+4х2≤19906x1+5х2≤321012x1+10x2≤4210
По смыслу задачи переменные х1 ≥ 0, х2 ≥0.
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.
Суммарная прибыль составит 8х1 от реализации продукции I и 9х 2 от реализации продукции II, то есть : F = 8х1 +9х 2. →max.
1. Построим область допустимых решений, т.е. решим графически систему неравенств.
Границей неравенства 13x1+4x2≤1990 является прямая 13x1+4x2=1990 , построим ее по двум точкам:
х1 0 1990/13
х2 497.5 0
Произвольная точка (0; 0) удовлетворяет неравенству 13x1+4x2≤1990 , поэтому областью решения неравенства будут точки, лежащие ниже прямой 13x1+4x2=1990 . Область решения обозначим штриховкой.
Границей неравенства 6x1+5x2≤3210 является прямая 6x1+5x2=3210 , построим ее по двум точкам:
х1 0 535
х2 642 0
Произвольная точка (0; 0) удовлетворяет неравенству 6x1+5x2≤3210 , поэтому областью решения неравенства будут точки, лежащие ниже прямой 6x1+5x2=3210 . Объединим полученную полуплоскость с ранее найденными ограничениями. Область решения обозначим штриховкой.
Границей неравенства 12x1+10x2≤4210 является прямая 12x1+10x2=4210 , построим ее по двум точкам:
х1 0 2105/6
х2 421 0
Произвольная точка (0; 0) удовлетворяет неравенству 12x1+10x2≤4210 , поэтому областью решения неравенства будут точки, лежащие ниже прямой 12x1+10x2=4210
. Объединим полученную полуплоскость с ранее найденными ограничениями. Область решения обозначим штриховкой.
Общая часть всех полуплоскостей область АВСDE является областью решений системы линейных неравенств.
Строим вектор-градиент целевой функции FX=8x1+9x2:∇F=8;9.(координаты вектора-градиента – частные производные функции ).
Проводим линию линейной функции перпендикулярно вектору-градиенту.
Для отыскания точки, соответствующей максимальному значению функции, сдвигаем линию уровня параллельно самой себе в направлении, указанном вектором ∇F.
Максимального значения функция достигает в точке: F(В), В(0,421)
Fmax=FВ=9∙351+8*0=3789.
Значит необходимо выпускать 421 ед изделий вида II, изделия вида I не выпускать, чтобы получить максимальную прибыль в размере 3789 ден ед
2. Следовательно, двойственная задача линейного программирования будет иметь вид:F(Y)=1990Y1+3210Y2+4210Y3 (min)
Ограничения:
13Y1 + 6Y2 + 12Y3
≥ 8
4Y1 + 5Y2 + 10Y3
≥ 9
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
В исходной задаче x1>0, х2>0. Следовательно, в двойственной задаче оба ограничения должны выполняться как равенства на оптимальном плане.
13y1+6y2+12y3=84y1+5y2+10y3=9
В исходной задаче на плане xопт равенствами являются 3-е ограничения
Задать вопрос
на новый заказ в Автор24.
