23. Визначення опорного плану транспортної задачі (метод подвійної переваги, метод апроксимації Фогеля

Метод мінімального елемента. В методі північно-західного кута на кожному кроці потреби першого з пунктів призначення, які залишилися задовольнялись за рахунок запасів першого з пунктів відправлення, які залишилися. Очевидно, вибір пунктів призначення і відправлення доцільно робити, орієнтуючись на тарифи перевезень, а саме: на кожному кроці потрібно вибирати яку-небудь клітинку, яка відповідає мінімальному тарифу (якщо таких клітинок декілька, то потрібно вибрати будь-яку з них), і розглянути пункти призначення і відправлення, які відповідають вибраній клітинці. Суть методу мінімального елемента і полягає в виборі клітинки з мінімальним тарифом. Потрібно відмітити, що цей метод, як правило, дозволяє найти опорний план транспортної задачі, при якому загальна вартість перевезень вантажу менша, ніж загальна вартість перевезень при плані, знайденому для даної задачі з допомогою північно-західного кута. Тому найбільш доцільно опорний план транспортної задачі знаходити методом мінімального елемента.

Метод апроксимації Фогеля. При визначенні оптимального плану транспортної задачі методом апроксимації Фогеля на кожній ітерації по всіх стовбцях і по всіх рядках знаходять відмінність між двома записаними в них мінімальними тарифами. Ці відмінності записують в спеціально відведених для цього рядку і стовбці в таблиці умов задачі. Серед вказаних відмінностей вибирають мінімальну. В рядку (або стовбці), якій відповідає дана відмінність, визначають мінімальний тариф. Клітинку, в якій він записаний, заповнюють на даній ітерації.

Якщо мінімальний тариф однаковий для декількох клітинок даного рядка (стовбця), то для заповнення вибирають ту клітинку, яка знаходиться в стовбці (рядку), який відповідає найбільшій відмінності між двома мінімальними тарифами, які знаходяться в даному стовбці (рядку).

24. Визначення оптимального плану транспортної задачі (метод потенціалів).

Оптимальний план - план, при якому цільова функція приймає мінімальне значення.

Після визначення опорного плану відбувається подальше його поліпшення за допомогою методів потенціалів.

Кожному рядку і кожному стовпцю в таблиці приписуються відповідні величини (потенціали), що визначаються з умови, що для ненульових осередків αi + βj = Cij. Оцінок буде рівно стільки скільки стовпців і рядків в сумі. Так як кількість рівнянь n + m-1, а невідомих оцінок n + m, то при визначенні оцінок один задається довільно, а наступні визначаються щодо її. Після цього складають матрицю оцінок, які обчислюються так: Δij = αi + βj-Cij. Якщо всі оцінки Δij будуть ≤ 0, то це буде оптимальний план. Якщо ні, то переходимо до нового плану.

Зміна вихідного плану здійснюється на підставі циклу перерахунку. Цикл перерахунку - замкнута ламана лінія, вершини якої знаходяться в ненульових осередках і в комірці (*); ланки утворюють прямі кути і розташовуються уздовж рядків і стовпців (у кожній вершині циклу зустрічаються тільки 2 ланки).

Побудова нового опорного плану відбувається таким чином: серед позитивних оцінок вибирається максимальна. Відповідна їй осередок повинна буде бути збільшена. Її позначають *. З неї починають будувати цикл перерахунку. Вершинам циклу, після цього, приписують почергово значення + або -, що означають, що у відповідних осередках значення чи збільшиться, або зменшиться. Величина, на яку змінюються ці значення, визначається мінімальним значенням осередки зі знаком «-».

Після цього знову обчислюють оцінки і перевіряють план на оптимальність