Метод найменшої вартості

Методи побудови початкового опорного плану

Як і в симплексному методі розв’язування задач лінійного програмування, при розв’язуванні транспортної задачі потрібно мати початковий опорний план.

Розглянемо методи знаходження цього плану:

1. Діагональний метод (північно-західного кута).

Побудову початкового опорного плану за методом північно-західного кута починають із заповнення лівої верхньої клітинки таблиці A ₁ B ₁ (х ₁₁), в яку записують менше з двох чисел а ₁ та b ₁. Далі переходять до наступної клітинки в рядку або стовпчику і заповнюють її і т.д., закінчуючи останньою правою клітинкою таблиці A_mB_n (х_mn).

Розглянемо алгоритм побудови початкового опорного плану транспортної задачі методом північно-західного кута:

1. Перевірка транспортної задачі на закритість. Якщо вона відкрита, то приводимо її до задачі закритого типу введенням або фіктивного постачальника або фіктивного споживача.

2. Першою заповнюємо верхню ліву клітинку. Заповнення клітинки A_iB_j таблиці здійснюємо за такими правилами:

а) якщо а_i < b_j, тобто запаси менші від потреб, то в цю клітинку записуємо весь об’єм запасу вантажу а_i, перераховуємо потреби споживача B_j, постачальника A_i вилучаємо з розгляду (наприклад, поставивши у всіх клітинках рядочка, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки A_i+1B_j;

б) якщо а_i > b_j, тобто запаси більші від потреб, то в цю клітинку записуємо весь об’єм потреб вантажу b_j, перераховуємо запаси постачальника A_i, вилучаємо з розгляду споживача B_j (ставимо у всіх клітинках стовпчика, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки A_iB_{j+ 1};

в) якщо а_i = b_j, тобто запаси рівні потребам, то в цю клітинку записуємо весь об’єм потреб чи запасів, вилучаємо з розгляду постачальника A_i і споживача B_j (ставимо в усіх клітинках стовпчика і рядка, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки A_i+1B_j+1.

3. Серед незаповнених клітинок (без обсягу вантажу і прочерків) знову вибираємо верхню ліву клітинку таблиці і заповнюємо її за правилами, поданими в п. 2. Так продовжуємо до тих пір, доки не заповнимо всі клітинки таблиці.

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

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

Після побудови початкового опорного плану кожним з методів у таблиці ма’ бути заповнено (т+п-1) клітинок, тому що ранг матриці системи обмежень транспортної задачі рівний r=m+n-l, де т- кількість постачальників, п - кількість споживачів. Заповнені клітинки називаються базисними, а незаповнені - вільними. Якщо кількість базисних клітинок рівна (т+п-1), то такий план називається невиродженим. Якщо кількість заповнених клітинок менша (т+п-1), то план називається виродженим. Тоді необхідно заповнити відповідну кількість порожніх (небазисних) клітинок, записуючи в них «нульове перевезення», і ці клітинки вважати базисними. Коли ж кількість заповнених клітинок перевищує (т+п-1), то початковий опорний план побудовано неправильно і він не є опорним.

Дата добавления: 2014-11-18