мента. p align="justify"> В) Метод апроксимації Фогеля .
При визначенні оптимального плану задачі методом апроксимації Фогеля на кожній ітерації по всіх стовпцях і по всіх рядках знаходять різницю між двома записаними в них мінімальними продуктивності. Ці різниці записують у спеціально відведених для цього рядку і стовпці в таблиці умов завдання. Серед зазначених різниць вибирають мінімальну. У рядку (або в стовпці), якої дана різниця відповідає, визначають мінімальну продуктивність. Клітку, в якій він записаний, заповнюють на даній ітерації. p align="justify"> Якщо мінімальна продуктивність однакова для декількох клітин цього рядка (стовпця), то для заповнення вибирають ту клітку, яка розташована у стовпці (рядку), відповідному найбільшій різниці між двома мінімальними продуктивністю, що знаходяться в даному стовпці (рядку ).
Зважаючи на виняткову практичної важливості завдання оптимального закріплення операцій за верстатами і специфіки її обмежень (кожна невідома входить лише в два рівняння систем (2) і (3) і коефіцієнти при невідомих дорівнюють одиниці) для вирішення завдання розроблені спеціальні методи. Деякі з них з них - метод потенціалів і розподільний методи - розглянуті нижче. p align="justify"> А) Метод потенціалів
Загальний принцип знаходження оптимального рішення задачі методом потенціалів аналогічний принципу вирішення завдання лінійного програмування симплексним методом, а саме: спочатку знаходять опорний план завдання, а потім його послідовно покращують до отримання оптимального плану.
Для визначення опорного плану транспортної задачі будемо користуватися одним з методів, розглянутих вище. Ці методи гарантують отримання зайнятих у вихідному плані п + т -1 кліток, причому в деяких з них можуть стояти нулі. Отриманий план слід перевірити на оптимальність.
Якщо для деякого опорного плану завдання існують такі числа що:
В В
при (8)
при (9)
для всіх і , то Х * = ( ) - оптимальний план розв'язуваної задачі.
Числа а i і b j; називаються потенціалами.
Сформульована теорема дозволяє побудувати алгоритм знаходження рішення задачі закріплення операцій за верстатами. Він полягає в наступному. Нехай одним з розглянутих вище методів знайдений опорний план завдання. Для кожного з верстатів і операцій визначають потенціали а i і b j . Ці числа знаходять із системи рівнянь
(10)
де з ij - продуктивність, що стоїть в заповнених клітках таблиці умов завдання.
Так як число заповнених клітин одно п + m -1, то система (10) з п + m невідомими містить n + m -1 рівнянь....
