Автор работы: Пользователь скрыл имя, 02 Октября 2011 в 19:02, контрольная работа
Дано: Для производства двух видов продукции А и В можно используется сырьё трёх видов. При этом на изготовление единицы изделия А расходуется 2 ед. сырья первого вида, 4 – ед. 2-го и 3 – ед. 3-го вида. На изготовление единицы изделия В расходуется 3 ед. сырья 1-го вида, 2 – ед. 2-го вида, 5 – ед. 3-го вида сырья. На складе фабрики имеется сырья 1-го вида 35 ед., 2-го – 42, 3-го – 49 ед. От реализации единицы готовой продукции А фабрика имеет прибыль 3 тыс. руб., а от продукции В прибыль составляет 3 тыс. руб.
СОДЕРЖАНИЕ
1.Симплексный метод в линейном программировании.
2.Двойственность в линейном программировании.
3.Транспортная задача.
4.Сетевое планирование и управление. Расчёт основных показателей.
Библиографический список.
Для модели предыдущей задачи составить двойственную, из симплексной таблицы найти ее решение и проверить по основной теореме.
Решение: Экономической сутью переменных двойственной задачи является определение оценок на ресурсы.
Для данной задачи составим двойственную.
z = 3x1
+ 3x2
2х1 + 3х2 35, y1
4х1
+ 2х2
3х1
+ 5х2
х1
Получим:
w
= 35y1 +42y2 +49y3
2y1 + 4y2 +3y3 3 x1
3y1
+ 2y2 + 5y3
yi
Соответствие между переменными исходной и двойственной задачами:
x3 x4 x5
y1
y2 y3
На основании симплексной таблицы получаем следующие решение двойственной задачи.
при
Проверка. .
Ответ: Наиболее дефицитным являются сырье 2 и 3 вида. Наименее дефицитным является сырье 1.
Дано: Из пунктов Ai, i= нужно перевезти ai, i= единиц груза соответственно, в пункты Bj, j= в количествах bj, j= соответственно. Затраты на перевозку 1 единицы груза из пункта Ai в Bj заданы в виде матрицы С=((сij)).
Найти: Найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.
Решение: По методу «северо – западного» угла оптимальный план имеет вид:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Число базисных клеток m+n – 1=4+5 – 1=8. Затраты на данный план:
По методу наименьшего элемента оптимальный план приобретет вид:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Число заполненных клеток m+n – 1=8. Затраты:
С помощью метода потенциалов проверим, оптимален ли план перевозок. Определим потенциалы строк – Ui и столбцов – Vj удовлетворяющие условию: Ui + Vj = Cij для базисных переменных (для занятых клеток). Зададим U1=0.
U1+V4=3 U1=0 V1=-1
U1+V5=2 U2=4 V2=-1
U2+V2=3 U3=3 V3=4
U2+V3=8 U4=3 V4=3
U2+V4=7
U3+V1=2
U3+V2=2
U4+V1=2
Определим характеристики для свободных неизвестных (пустых клеток) по формуле Eij = Cij – (Ui + Vj) и запишем в левом нижнем углу свободных клеток. План оптимален, если все Eij 0.
E11=7-(0-1) > 0,
E12=5-(0-1) > 0,
E13=4-(0-4) = 0,
E21=4-(4-1) > 0,
E25=6-(4+2) = 0,
E33=5-(3+4) = - 2,
E34=6-(3+3) = 0,
E35=9-(3+2) > 0,
E42=5-(3-1) > 0,
E43=6-(3+4) = - 1,
E44=6-(3+3) = 0,
E45=7-(4+2)
> 0.
Имеем две клетки с отрицательными оценками, выбираем с наименьшей оценкой E33. Строим контур для клетки А3В3:
А33
Вершинам
присваиваем чередующиеся знаки
плюс – минус, выбираем наименьшую
поставку
Количество
груза в ''положительных'' вершинах увеличивается
на 35, а в ''отрицательных'' уменьшается
на 35. Θmin(35;125)=35 ,Δz=-2*35=-70 Получаем следующий
план перевозок:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||