- •Побудова математичної моделі задачі лінійного програмування
- •2. Перетворення задач лінійного програмування до канонічної форми запису
- •3. Розв’язання задачі лінійного програмування симплекс-методом
- •4. Побудова двоїстої задачі
- •5. Економічна інтерпретація задач двоїстої пари
- •Теоретичний матеріал для виконання завдання №3
- •1. Постановка транспортної задачі
- •Дослідження чутливості величини прибутку при зміні ресурсів
- •Теоретичний матеріал для виконання завдання №2
- •Постановка та математична модель задачі розподілу виробничої програми по видах взаємозамінного обладнання.
- •Приклад розв’язання задачі розподілу виробничої програми.
- •2. Метод північно-західного кута
- •3. Метод найменших вартостей
- •3. Метод потенціалів
- •5. Приклад розв’язання незбалансованої транспортної задачі
- •Теоретичний матеріал для виконання завдання №4
- •1. Постановка задачі комівояжера
- •Представлення задачі комівояжера у виді графа
- •Метод гілок і границь
- •4.11. Застосування методу гілок і границь до розв’язання задачі комівояжера
- •Приклад розв’язання задачі про обробку деталей
2. Метод північно-західного кута
Згідно з цим методом заповнюють клітинки матриці перевезень, починаючи з лівого верхнього кута, послідовно вичерпуючи всі запаси. Детальніше проілюструємо це на прикладі матриці перевезень, заданої табл. 3.3.
Таблиця 3.3
Пункт відправлення |
Пункт споживання |
Запас |
||||
B1 |
B2 |
B3 |
B4 |
B5 |
||
A1 |
4
|
1 |
3 |
4 |
4 |
60 |
A2 |
2
|
3 |
2 |
2 |
3 |
35 |
A3 |
3
|
5 |
2 |
4 |
4 |
40 |
Потреба |
22 |
45 |
20 |
18 |
30 |
135 |
Першою заповнюється клітинка А1В1. В неї заноситься min(22,60)=22. Потреба В1 повністю покрита, тому цей стовпець далі не розглядається (можна викреслити). У залишеній таблиці наступною північно-західною клітинкою буде А1В2. Залишок запасу для А1 становитиме 60-22=38. В А1В2 заносимо min(45,38)=38. Запас для A1 повністю покритий (викреслюємо рядок). В А2В2 заносимо min(45-38,35)=7. Викреслюємо В2 і т.д. Отримуємо таблицю 3.4.
Таблиця 3.4
Пункт відправлення |
Пункт споживання |
Запас |
||||
B1 |
B2 |
B3 |
B4 |
B5 |
||
A1 |
4 22 |
1 38 |
3 |
4 |
4 |
60|38|0 |
A2 |
2
|
3 7 |
2 20 |
2 8 |
3 |
35|28|8|0 |
A3 |
3
|
5 |
2 |
4 10 |
4 30 |
40|30|0 |
Потреба |
22 0 |
45 7 0 |
20 0 |
18 10 0 |
30 0 |
135 |
3. Метод найменших вартостей
Цей метод аналогічний методу північно-західного кута, проте числа заносяться у клітинку з найменшим значенням вартості у залишеній таблиці (проте фіктивний пункт завжди розглядається останнім). Проілюструємо на прикладі. Найменшу вартість має клітинка А1В2. Тому першою заповнюємо її. Заносимо в неї min(45,60)=45 і викреслюємо стовпець В2. Далі вибираємо найменшу вартість - 2. Оскільки вона відповідає кільком клітинкам, вибираємо будь-яку з них, наприклад А2В1 - min(35,22)=22. Викреслюємо В1. Потім в А2В3 - min(20,13)=13, викреслюємо А2 і т.д. Результат у табл. 3.5.
Таблиця 3.5
Пункт відправлення |
Пункт споживання |
Запас |
||||
B1 |
B2 |
B3 |
B4 |
B5 |
||
A1 |
4
|
1 45 |
3 |
4 |
4 15 |
60|15|0 |
A2 |
2 22 |
3
|
2 13 |
2
|
3 |
35|13|0 |
A3 |
3
|
5 |
2 7 |
4 18 |
4 15 |
40|33|0 |
Потреба |
22 0 |
45 0 |
20 7 0 |
18 0 |
30 15 0 |
135 |
Зауваження 3.1. Число базисних клітинок повинно бути m+n-1, інакше їх доповнюють до відповідної кількості з числа вільних клітинок із базисним значенням 0.
