Автор работы: Пользователь скрыл имя, 18 Декабря 2012 в 22:24, контрольная работа
Фірма для автомобільної промисловості виготовляє деталі двох типів А і В. Для їх виготовлення фірма має фонд робочого часу 4000 годин на тиждень. Для виготовлення однієї деталі типу А потрібно використати одну год., а типу В – 2 години. Потужність фірми дозволяє виготовити деталей типу А максимум 2250 од., а типу В - 1750 од. за тиждень. Кожна деталь типу А потребує 2 кг металевих стрижнів та 5 кг листового прокату, а для виготовлення деталі типу В потрібно 5 кг металевих стрижнів та 2 кг листового прокату.
З даної таблиці знаходимо вираз для вільної змінної и3:
и3 = - и1 – 7и2 – v 2 + 50
та із подальшого розгляду виключаємо другий стовпець.
Табл. 4.3 не містить опорного розв'язку, бо в стовпці вільних елементів є від'ємні. Для його знаходження проглядаємо другий рядок із від'ємним вільним, склавши невід'ємні відношення вільних елементів до відповідних елементів першого стовпця, бачимо, що найменше відношення утворене із елементом – 3.
З цим елементом здійснюємо крок МЖВ і отримуємо табл. 4.4.
Таблиця 4.4.
VI = |
У3 = |
У4 = |
\\> = | ||
| - х2 |
- х3 |
- х4 |
1 | |
И1 |
У1 = |
5/3 |
-31/3 |
- 10 |
- 49 |
И2 |
У2 = |
-23/3 |
13/3 |
- 3 |
-15 |
V1 |
Х1 = |
-1/3 |
5/3 |
1 |
8 |
1 |
z = |
130/3 |
-50/3 |
15 |
160 |
Аналогічно попередньому із елементом а13 здійснюємо наступний крок МЖВ і одержуємо табл. 4.5.
Таблиця 4.5.
У3 = |
И1 = |
У2 | |||
| - х2 |
-х3 |
- у1 |
1 | |
V1 |
Х4 = |
-1/6 |
31/30 |
-1/10 |
-49/10 |
и2 |
У2 = |
-49/6 |
223/30 |
3/10 |
-3/10 |
VI |
Х1= |
-1/6 |
19/30 |
1/10 |
31/10 |
1 |
z |
275/6 |
193/6 |
3/2 |
173/2 |
Далі, здійснивши крок МЖВ з елементом а 23 = - 3/10,
остаточно маємо табл. 53.
Таблиця 4.6.
V 2 = |
V 3 = |
и2 = |
W = | ||
| -х2 |
-х3 |
- у2 |
1 | |
V4 |
Х4 = |
5 | |||
И1 |
У = |
1 | |||
V1 |
Х1= |
3 | |||
1 |
z = |
5 |
209/3 |
5 |
85 |
В останній таблиці наявність додатних вільних елементів та додатних коефіцієнтів 2 -рядка про те, що опорний розв'язок знайдено, і цей розв'язок є оптимальним для цільової функції.
Із табл. 4.6. знаходимо розв'язок прямої задачі:
W мах = 85 х (х2 - х3 = У2 = 0, х1 = 3, х4 =5, у1 = 1)
та спряженої задачі:
W мін = 85 (и1 = V1 = V4 = 0, V2 = 5, V3 = 208/3, и2 = 5).
5. Транспортна задача.
Знайти оптимальний розв'язок транспортної задачі за критерієм мінімальних сукупних витрат за перевезення, якщо вектор запасу вантажу в пунктах постачання А = {1ОО; 15О; 2ОО; 25О}, вектор потреб
В- {12О;8О;2ОО} та матриця тарифів перевезень
10 5 3
8 10 6
С = 4 9 2
11 5 2
Розв'язування:
Перевіряємо умову балансову : Σаі = Σві.
Σаі =100+150+200+250=700,
Σві=120 + 80+200 = 400.
Як бачимо, балансову умову не виконано - «потреб» менше ніж «можливостей» постачальників. Вводимо «фіктивного» споживача з потребами 700-400=300 одиниць з нульовим тарифом за перевезення.
З врахуванням фіктивного споживача дані «закритої моделі» задачі записуємо в транспортну таблицю, в якій знаходимо опорний розв'язок методом подвійних відміток, оптимальність якого перевіряємо методом потенціалів.
Таблиця 5.
120 |
80 |
200 |
300 |
||
100 |
30 |
70 |
0 | ||
150 |
150 |
0 | |||
200 |
120 |
80 |
0 | ||
250 |
50 |
200 |
0 |
0 | |
vJ |
4 |
5 |
2 |
0 |
Як бачимо, знайдений опорний розв'язок з матрицею перевезень
0 30 0 70
Хіj = 0 0 0 150
120 0 0 80
0 50 200 0
задовольняє умови потенціальності, що означає його оптимальність. При цьому найменша вартість перевезень складає:
Qмін = 30 - 5 + 120 - 4 + 50 - 5 + 200 - 2 = 1280 грн.
Відповідь: 1280 грн.