- •Правила виконання та оформлення контрольної роботи
- •Програма курсу
- •Методичні вказівки до контрольної роботи Предмет, особливості та сфери застосування оптимізаційних методів та моделей в економіці
- •Загальний вигляд задачі лінійного програмування. Різні форми запису задач лінійного програмування
- •Графічне розв’язування задачі лінійного програмування
- •Алгоритм знаходження оптимальних значень цільової функції графічним методом
- •Теорія двоїстості в лінійному програмуванні
- •Правила побудови двоїстої задачі:
- •Економічна постановка задачі, її математична модель.
- •Двоїстий симплекс-метод
- •Алгоритм методу потенціалів складається з таких етапів:
- •Метод північно-західного кута.
- •Метод мінімальної вартості.
- •Ігрові моделі в управлінні економічним ризиком
- •Варіанти контрольної роботи
- •1.1. Побудова економіко-математичних моделей задачі.
- •1.2. Знаходження розв’язку задачі лінійного програмування графічним методом
- •1.3. Двоїсті задачі.
- •1.4. Транспортна задача лінійного програмування
- •1.5. Матрична гра
- •Література
Алгоритм методу потенціалів складається з таких етапів:
Визначення типу ТЗ (збалансована чи незбалансована). У другому випадку – збалансувати.
Побудова першого опорного плану ТЗ.
Визначення потенціалів опорного плану ТЗ.
Перевірка опорного плану ТЗ на оптимальність. Якщо умова оптимальності не виконується, то повторити дії, починаючи з п.3.
1. Як збалансувати ТЗ було розглянуто раніше. Переходимо до п.2.
2. Для побудови початкового опорного плану транспортної задачі існує кілька методів: північно-західного кута; мінімальної вартості; подвійної переваги, метод Фогеля та інші. Побудову опорного плану зручно подавати у вигляді таблиці, в якій постачальники продукції визначаються рядками, а споживачі - стовпчиками.
Метод північно-західного кута.
Таблиця
заповнюється починаючи з лівого верхнього
кута (північно-західного кута), рухаючись
далі по рядку вправо, або по стовпчику
вниз. У клітинку (1.1)
заноситься
менше з чисел
та
,
тобто
.
Якщо
,
то
і перший стовпчик закритий для заповнення
інших його клітинок, тобто
для
(потреби першого споживача задоволені
повністю). Далі рухаються
по першому рядку в клітинку (1.2). У ній
записується менше з чисел
та
,
тобто
.
Якщо
,
то
аналогічно закривається перший рядок,
тобто
і
для
.
Далі заповнюється клітинка (2.1), в яку
заноситься
.
Заповнивши клітинку (1.2). або (2.1), переходять до заповнення третьої клітинки або по другому рядку, або по другому стовпчику. Цей процес продовжують до повного вичерпування продукції у пунктах, або повного задоволення потреб споживачів. Остання заповнена клітинка виявиться в останньому -му рядку та -му стовпчику.
План, отриманий методом північно-західного кута, буде опорним планом системи обмежень транспортної задачі.
Приклад 4. Методом північно-західного кута знайти опорний план ТЗ, умова якої задається таблицею:
Постачальники |
Споживачі |
Запаси |
|||||||
1 |
2 |
3 |
4 |
||||||
1 |
|
6 |
|
7 |
|
3 |
|
5 |
100 |
75 |
|
25 |
|
|
|
|
|
||
2 |
|
4 |
|
2 |
|
5 |
|
6 |
150 |
|
|
55 |
|
60 |
|
35 |
|
||
3 |
|
3 |
|
10 |
|
20 |
|
1 |
50 |
|
|
|
|
|
|
50 |
|
||
Потреби |
75 |
80 |
60 |
85 |
|
||||
Опорний план:
Недоліком такого підходу до знаходження початкового опорного плану транспортної задачі є те, що у процесі визначення обсягів перевезень за маршрутами не враховують нормативи витрат на транспортування. Тому необхідно врахувати витрати при визначенні початкового опорного плану.
