Розстановка потенціалів і перерозподіл поставок
Операція 1.2. Перевірка небазисних клітин на відповідність їх умові оптимальності.
Оптимальний план транспортної задачі повинен відповідати критерію оптимальності, який виражається в тому, чи відповідають небазисних клітини матриці умові, що формуються наступним виразом:
. ( 1.8)
Якщо ця умова для всіх небазисних клітин виконується, то план є оптимальним, а якщо немає, хоча б для однієї клітини, то план не оптимальний. Інакше кажучи, існує деякий план з меншим функціоналом. Різниця потенціалів може інтерпретуватися як деяка умовна ціна перевезення одиниці продукції по маршруту, що зв'язує відповідні станції «i» та «j». Якщо вона нижче cij, значить, використання даного маршруту не поліпшить план, а якщо cij нижче різниці потенціалів, т. Е. Умова ( 1.8) не виконується, отже, існує план краще розрахованого, який необхідно відшукати.
Перевіримо умову ( 1.8) для табл. 1.6.
Клітка А1В1: 4 - 5 <10, умова виконується.
Клітка А1В2: 7 - 5 <9, умова виконується і т. Д.
Якщо для всіх небазисних клітин умова 3 виконується, то розглянутий план буде оптимальний. Подальші дії переходять за алгоритмом до операції 4.
Однак для нашого прикладу це не так. Чи не виконується умова для клітини А2В4 (10 - 0> 6), клітини А3В3 (13 - 1> 9), а також для клітин А3В4, А4В3, з чого випливає, що розроблений опорний план не оптимальний. Відзначимо ці клітини.
Операція 3. Поліпшення плану.
|
|
|
Оскільки отриманий план не оптимальний, подальші дії алгоритму полягають в його перетворенні в кращу сторону або просто поліпшення.
Операція 3.1. Побудова ланцюга (контуру, циклу) перерозподілу поставок.
Поліпшення плану здійснюється по одній з небазисних клітин, для якої умова оптимальності виявилося невиконаним. У нашому плані є чотири такі клітини. Вибираємо одну з них, для якої умова оптимальності не виконується в найбільшою мірою. У нашому плані це клітина А2В4. Для неї умова оптимальності не виконана на 4 одиниці (10 - 0 - 6 = 4). Для цієї клітини будуємо ланцюг перерозподілу поставок. Ланцюг перерозподілу поставок - це така замкнута ламана лінія, яка проходить по клітинам матриці ходом шахової тури. У вершинах контуру обов'язково лежить одна небазисна клітина (невідповідна умові оптимальності, знайдена раніше), а інші відповідають тільки базисним клітинам. Лінії контуру можуть перетинатися. Для небазисної клітини А2В4 ланцюг буде проходити по клітинам А1в4, А1В3, А2В3 (табл. 1.7).
Таблиця 1.7
Можливі варіанти побудови циклу перерозподілу
У нашому випадку форма ланцюга проста. Однак ланцюг може мати будь-яку форму, в тому числі і химерну (див. Табл. 1.7). Її потрібно навчитися знаходити, використовуючи евристичні підходи. При цьому необхідно враховувати, що кожна небазисна клітина транспортної матриці обов'язково має одну ланцюг перерозподілу поставок.
|
|
|
Дата добавления: 2019-09-02; просмотров: 170; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!