r/>В В
2.1 Методи рішення задачі оптимального закріплення операцій за верстатами
Для вирішення задачі оптимального закріплення операцій за верстатами необхідно знайти опорний план, який при подальшому вирішенні буде неодноразово змінюватися і оптимізуватися. Пошук опорного плану рішення задачі можна зробити за допомогою декількох методів, опис кожного буде приведено ниже:
А) Метод північно-західного кута
Б) Метод найменших витрат
В) Метод апроксимації Фогеля
Як нам відомо, число змінних Х ij в задачі з т кількістю верстатів і п кількістю операцій одно пт, а число рівнянь в системах одно п + т . Так як ми припускаємо, що виконується умова рівності потреби в операціях кількості верстатів, то число лінійно незалежних рівнянь дорівнює п + т - 1. Отже, опорний план задачі може мати не більше п + т - 1 відмінних від нуля невідомих.
Якщо в опорному плані число відмінних від нуля компонент одно в точності п + т - 1, то план є невиродженим , а якщо менше - то виродженим. транспортний завдання оптимальний закріплення
Як і для всякої задачі лінійного програмування, оптимальний план задачі закріплення операцій за верстатами є і опорним планом. Перейдемо до опису кожного з названих методів. p align="justify"> Сутність цих методів полягає в тому, що опорний план знаходять послідовно за п + т - 1 кроків, на кожному з яких у таблиці умов завдання заповнюють одну клітку, яку називають зайнятою. Заповнення однієї з клітин забезпечує повністю або задоволення потреби в операції одного з верстатів (того, у стовпці якого знаходиться заповнена клітка), або відсутність виконання даної операції на даному верстаті ( з того, у рядку якого знаходиться заповнюється клітка).
У першому випадку тимчасово виключають з розгляду стовпець, що містить заповнену на даному кроці клітку, і розглядають задачу, таблиця умов якої містить на один стовпець менше, ніж було перед цим кроком, але те ж кількість рядків і відповідно змінені потреби в операціях в одному з пунктів (у тому, за рахунок запасу якого була задоволена потреба в операціях верстата на даному кроці). У другому...
