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

Іншими словами, для кожноїбазисної змінної поточного рішення

потенціалиіповинні задовольняти рівнянню:

Ці рівняння приводять до системи, що складається зрівнянь, в яких

фігурують невідомих. Таким чином, якщо однієї з невідомих

привласнити довільне значення і вирішити систему зрівнянь, то

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

коефіцієнти при цихзмінних в-рівнянні. Для задачі мінімізації вхідне рівняння може бути записане з отриманого канонічного виразу в наступному виді:

Базуючисьна умові оптимальності, можна записати значення коефіцієнтів при вільних зміннихокремо для транспортної задачі максимізації і задачі

мінімізації.

Для задачі мінімізації значення коефіцієнтів при вільних змінних в

рівнянні, повинні бути негативними

тоді оцінки для вільних змінних

повинні бути негативними, щобзменшилось при збільшенні . Таким

чином, для включення в базис вибирається вільна змінна , що має

найбільшу негативну оцінку

Для задачі максимізації значення коефіцієнтів в- рівнянні повинні бути позитивними

тоді оцінки для вільних змінних

повинні бути позитивними,щоб збільшувалося при збільшенні . Для включення в базис вибирається вільна змінна , що має найбільшу позитивну оцінку. Якщо в- рівнянні змінити знаки на протилежні, то поставлена задача буде вирішуватися, як задача мінімізації.

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

Таблиця 5

2. Визначаємо ціну циклу, вершинами якого є клітки:

Тому що ціна циклунегативна, то обрану вільну клітку варто вводити в новий базис.

Знайдемо змінну, що уводиться в базис, методом потенціалів.

Рішення 1. Для кожної базисної змінної отриманого початкового рішення запишемо

систему рівнянь щодо невідомих потенціалів,:

Приймемо , тоді в результаті рішення системи рівнянь одержимо

наступні значення потенціалів: , , , , ,

. Значення потенціалів проставляють ліворуч і зверху в табл. 6.

2. Знайдемо оцінки для небазисних змінних в розв'язаній задачі мінімізації. У

цьому випадку справедливе співвідношення, тобто

для включення в базис варто вибирати ту вільну змінну, яка має найбільшу

негативну оцінку:

Таким чином, з отриманих оцінок найбільше негативне значення має оцінка. Отже, зміннавибирається як уведена в новий базис.

Таблиця 6

Потенціали і можна визначити безпосередньо з транспортної

таблиці, якщо врахувати, що в зайнятих клітках сума повинна

дорівнювати. Спрощується також обчислення оцінок для небазисних змінних, якщо для кожної вільної кліткизнайти спочатку суму потенціалів , а потім відняти її з величини вартості, що стоїть на перетинанні рядкаі стовпця.

Варіанти

ПН

ОП

В1

В2

В3

В4

В5

Обсяги пунктів відправлення

А1

4

2

5

1

1

35+6l

А2

1

3

0

4

4

5+6n

А3

6

0

2

3

5

10+8m

Обсяги пунктів призначення

10+l+n+m

10+2l+n+m

10+l+2n+m

10+l+n+2m

10+l+n+3m

l – Остання цифра номера залікової книжки

n – Остання цифра в списку групи

m – Номер групи

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11