Автор: Пользователь скрыл имя, 11 Марта 2012 в 10:45, задача
Задача 2.
Для производства четырех видов продукции используется 3 вида сырья Нормы расхода сырья (кг) запасы (кг) его ценности от реализации единицы продукции заданы таблицей.
Составить план выпуска продукции, обеспечивающей получение максимальной прибыли, используя симплексный метод, а также построить двойственную задачу и решить ее симплекс методом.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Оптимальный план можно записать так:
x5 = 13.33
x6 = 6.67
x2 = 16.67
F(X) = 7*16.67 = 116.67.
Составим двойственную задачу.
Целевая функция в двойственной задаче определяет стоимость запасов всех ресурсов.
Левая часть ограничений определяет стоимость ресурсов в теневых (альтернативных) ценах, затраченных на xj.
3y1+9y2+12y3≥5.5
4y1+5y2+6y3≥7
10y1+12y2+15y3≥9
8y1+9y2+10y3≥11
80y1+90y2+100y3 → min
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
3y1+9y2+12y3+у4=5.5
4y1+5y2+6y3+у5=7
10y1+12y2+15y3+у6=9
8y1+9y2+10y3+у7=11
Умножим все строки на (-1) и будем искать первоначальный опорный план.
-3y1-9y2-12y3-у4=-5.5
-4y1-5y2-6y3-у5=-7
-10y1-12y2-15y3-у6=-9
-8y1-9y2-10y3-у7=-11
Базис | В | y1 | y2 | y3 | y4 | y5 | y6 | y7 |
у4 | -5.5 | -3 | -9 | -12 | 1 | 0 | 0 | 0 |
у5 | -7 | -4 | -5 | -6 | 0 | 1 | 0 | 0 |
у6 | -9 | -10 | -12 | -15 | 0 | 0 | 1 | 0 |
у7 | -11 | -8 | -9 | -10 | 0 | 0 | 0 | 1 |
Z(Y0) | 0 | 80 | 90 | 100 | 0 | 0 | 0 | 0 |
Θ | 0 | - | - | - | - |
Базис | В | y1 | y2 | y3 | y4 | y5 | y6 | y7 |
у4 | 7.7 | 6.6 | 1.8 | 0 | 1 | 0 | 0 | -1.2 |
у5 | -0.4 | 0.8 | 0.4 | 0 | 0 | 1 | 0 | -0.6 |
у6 | 7.5 | 2 | 1.5 | 0 | 0 | 0 | 1 | -1.5 |
y3 | 1.1 | 0.8 | 0.9 | 1 | 0 | 0 | 0 | -0.1 |
Z(Y1) | -110 | 0 | 0 | 0 | 0 | 0 | 0 | 10 |
Θ | 0 | - | - | - | - | - | - | - |
Базис | В | y1 | y2 | y3 | y4 | y5 | y6 | y7 |
у4 | 8.5 | 5 | 1 | 0 | 1 | -2 | 0 | 0 |
y7 | 0.67 | -1.33 | -0.67 | 0 | 0 | -1.67 | 0 | 1 |
у6 | 8.5 | 0 | 0.5 | 0 | 0 | -2.5 | 1 | 0 |
y3 | 1.17 | 0.67 | 0.83 | 1 | 0 | -0.17 | 0 | 0 |
Z(Y1) | -116.67 | 13.33 | 6.67 | 0 | 0 | 16.67 | 0 | 0 |
Оптимальный план можно записать так:
y4 = 8.5
y7 = 0.67
y6 = 8.5
y3 = 1.17
Z(Y) = 100*1.17 = 116.67.
Задача 3. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны в1,в2,в3,в4 единицы. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны а1,а2,а3 единицы. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей.
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной. Задачу решить методом потенциалов.
Решение:
Поставщик | Потребитель | Запасы | |||||||||||||||||||
B1 | B2 | B3 | B4 | ||||||||||||||||||
A1 |
|
|
|
| 150 | ||||||||||||||||
A2 |
|
|
|
| 130 | ||||||||||||||||
A3 |
|
|
|
| 160 | ||||||||||||||||
Потребность | 100 | 150 | 80 | 70 |
| ||||||||||||||||
Транспортная задача является открытой, так как запас груза больше потребностей на 40 единиц. Приведем задачу к закрытому типу - введем фиктивного потребителя B5.
Поставщик | Потребитель | Запасы | ||||||||||||||||||||||||
B1 | B2 | B3 | B4 | B5 | ||||||||||||||||||||||
A1 |
|
|
|
|
| 150 | ||||||||||||||||||||
A2 |
|
|
|
|
| 130 | ||||||||||||||||||||
A3 |
|
|
|
|
| 160 | ||||||||||||||||||||
Потребность | 100 | 150 | 80 | 70 | 40 |
| ||||||||||||||||||||