Для производства различных изделий А и используется три вида сырья. На изготовление единицы изделия А требуется затратить сырья первого вида a1 кг, сырья второго вида – a2 кг, сырья третьего вида – a3 кг. На изготовление единицы изделия В требуется затратить сырья первого вида b1 кг, сырья второго вида – b2 кг, сырья третьего вида – b3 кг.
Производство обеспечено сырьем первого вида в количестве p1 кг, сырьем второго вида – p2 кг, сырьем третьего вида – p3 кг.
Прибыль от реализации единицы готового изделия А составит α руб., а изделия В – β руб.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Решить задачу симплексным методом путем преобразования симплекс-таблиц.
Решить задач графически.
a1 = 3, b1 = 5, p1 = 453, α = 2,
a2 = 4, b2 = 8, p2 = 616, β = 5.
a3 = 3, b3 = 11, p3 = 627,
Решение
Математическая модель задачи
Переменные задачи:
x1 – количество изделий А, ед;
x2 – количество изделий В, ед.
Тогда:
3x1+5x2 – затраченное сырье первого вида, кг;
4x1+8x2 – затраченное сырье второго вида, кг;
3x1+11x2 – затраченное сырье третьего вида, кг.
Ограничения:
Производство обеспечено сырьем первого вида в количестве 453 кг, сырьем второго вида – 616 кг, сырьем третьего вида – 627 кг. Значит, должны выполняться следующие неравенства:
3x1+5x2 ≤453(1)
4x1+8x2≤616(2)
3x1+11x2 ≤627(3)
По смыслу задачи переменные должны быть неотрицательными числами:
xi≥0, i=1,3(4)
Целевая функция:
Прибыль от реализации готового изделия А составляет 2 руб., а изделия В – 5 руб., тогда общая прибыль равна:
F=2x1+5x2(5)
Таким образом, получена математическая модель задачи:
Найти максимальное значение функции F=2x1+5x2→max при условиях:
3x1+5x2 ≤4534x1+8x2≤6163x1+11x2 ≤627xi≥0, i=1,3
Решение задачи графическим способом
Определение области допустимых решений (ОДР)
В неравенствах системы ограничений заменим знаки неравенств на знаки точных равенств и построим соответствующие им прямые.
l1:3x1+5x2=453
x2=90,6-0,6x1
Строим прямую l1 по двум точкам:
x1
0 160
x2
90,6 -5,4
l2: 4x1+8x2=616
x1+2x2=154
x2=77-0,5x1
Строим прямую l2 по двум точкам:
x1
0 160
x2
77 -3
l3: 3x1+11x2=627
x2=57-311x1
Строим прямую l3 по двум точкам:
x1
0 220
x2
57 -3
l4: x1=0 – ось абсцисс
l5: x2=0 – ось ординат
Строим полученные прямые (рис. 1).
Рис. 1. Прямые, определяющие неравенства системы органичений
Определяем полуплоскости, удовлетворяющие неравенствам системы ограничений: их пересечение образует область допустимых решений.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству системы ограничений, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-либо точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты исходному неравенству. Если удовлетворяют, то искомой является та полуплоскость, которой эта точка принадлежит; в противном случае – другая полуплоскость.
Прямая l1
Точка 0;0
Неравенство 3x1+5x2 ≤453
0+0≤453
0≤453 – верное
Т.е. выбираем полуплоскость, содержащую точку (0; 0)
Прямая l2
Точка 0;0
Неравенство 4x1+8x2≤616
0+0≤616
0≤616 – верное
Т.е. выбираем полуплоскость, содержащую точку (0; 0)
Прямая l3
Точка 0;0
Неравенство 3x1+11x2 ≤627
0+0≤627
0≤627 – верное
Т.е
. выбираем полуплоскость, содержащую точку (0; 0)
Четвертое и пятое неравенства определяют первую координатную четверть.
Построим область допустимых решений задачи линейного программирования (рис. 2).
Рис. 2. Область допустимых решений
Многоугольник ОABCD – область допустимых решений.
Определение оптитмального решения
Координаты любой точки, принадлежащей ОДР, удовлетворяют неравенствам системы ограничений и условию неотрицательности переменных. Поэтому исходная задача будет решена, если мы сможем найти точку, принадлежащую этой области, в которой целевая функция принимает максимальное значение.
Чтобы найти такую точку, построим прямую (линию уровня)2x1+5x2=h (где h –некоторая постоянная), проходящую через многоугольник решений.
Возьмем h=240 и построим прямую 2x1+5x2=240 по точкам:
x1
0 150
x2
48 -12
Вектор c(2;5) служит для определения направления перемещения линии уровня. В качестве вектора направления выберем вектор c1(8;20), сонаправленный вектору c. Перемещая линию уровня в направлении вектора c1, получаем, что последней общей точкой ее и области допустимых решений является точка В пересечения прямых l2 и l3. (рис. 3).
Рис. 3. Нахождение оптимального плана графическим методом
Для определения координат точки В составим и решим систему уравнений:
4x1+8x2=616 3x1+11x2=627 ⇔12x1+24x2=1848 12x1+44x2=2508 ⇔x1=(616-8x2)/4 20x2=660⇔x1=88x2=33
Найдем соответствующее значение целевой функции:
Fmax=2∙88+5∙33=341.
Таким образом, X*(88;33) – оптимальный план, при котором целевая функция принимает максимальное значение Fmax=341.
Т.е., максимальная прибыль, равная 341 руб, будет обеспечена при производстве 88 ед. изделий А и 33 ед. изделий В.
Решение задачи симплекс-методом
F=2x1+5x2→max
3x1+5x2 ≤4534x1+8x2≤6163x1+11x2 ≤627xi≥0, i=1,3
Запишем задачу в форме основной задачи линейного программирования. В системе ограничений перейдем от неравенств к равенствам, для чего введем дополнительные переменные x3,x4, x5 ≥0.
Система ограничений примет вид:
3x1+5x2+x3=4534x1+8x2+x4=6163x1+11x2+x5=627xi≥0, i=1,5
Целевая функция примет вид:
FX=2x1+5x2+0∙x3+0∙x4+0∙x5→max
Преобразованную систему ограничений можно записать в векторной форме:
x1Р1+x2Р2+x3Р3+x4Р4+x5Р5=Р0, где
Р1=343, Р2=5811, Р3=100, Р4=010, Р5=001, Р0=453616627
Для основной задачи можно записать опорный план X1=(0;0;453;616;627), который определяется системой единичных векторов Р3, Р4, Р5 (они образуют базис трехмерного пространства).
Составим первую симплекс-таблицу.
Таблица 1
№ Базис Сб
Р0
Переменные
2 5 0 0 0
1 x3
0 453 3 5 1 0 0
2 x4
0 616 4 8 0 1 0
3 x5
0 627 3 11 0 0 1
F=0 –2 –5 0 0 0
Опорный план: X1=(0;0;453;616;627).
F=2∙0+5∙0+0∙453+0∙616+0∙627=0
Найдем оценки:
∆j=i=13ciaij-cj
где cj – коэффициенты при неизвестных целевой функции,
aij – коэффициенты при неизвестных в системе ограничений, ci – коэффициенты при базисных переменных.
Оценки в столбцах базисных переменных равны 0: ∆3=∆4=∆5=0.
∆1=0∙3+0∙4+0∙3-2=-2
∆2=0∙5+0∙8+0∙11-5=-5
Поскольку среди есть отрицательные оценки, то опорный план не является оптимальным
Задать вопрос
на новый заказ в Автор24.
