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

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

Крок 1. Знаходиться комірка з найменшою вартістю. Якщо таких комірок декілька, то вибір з них довільний.

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

Крок 3. Викреслюємо стовпчик (рядок), для якого попит (пропозицію) задоволено. Якщо задоволено і попит і пропозицію, викреслюємо довільно або рядок або стовпчик. У викреслених стовпчиках та рядках пошук базисних змінних не ведеться. Повертаємося до кроку 1.

Застосуємо цей метод до нашої задачі. Координати комірок показуватимемо у форматі (i,j), де і - номер рядка-завода, j - номер стовпчика-салона.

Крок 1. Знайдемо комірки з найменшою вартість. Таких комірок дві (2,4) і (3,1). Тому оберемо одну з них довільно, наприклад, комірку (3,1).

Крок 2. Змінній у вибраній комірці присвоюється найбільше значення з можливих (х31=15). Це перша базисна змінна.

Крок 3. В комірці (3,1) задовольняється одночасно і попит і пропозиція, тому викреслюємо довільно рядок чи стовпчик. Виберемо, наприклад, стовпчик 1, так як це показано на рис. 4. Повертаємося до першого кроку.

Рис. 4

Крок 1 (4). Комірка з найменшою вартістю (2, 4)

Крок 2 (5). Змінній у вибраній комірці присвоюється найбільше значення з можливих (х24=15). Це друга базисна змінна.

Крок 3 (6). У 4-му стовпчику повністю задовольняється попит, тому викреслюємо його (див. рис. 5).

Рис. 5

Крок 1 (7). Комірка з найменшою вартістю (3, 3)

Крок 2 (8). Змінній у вибраній комірці присвоюється найбільше значення з можливих (0). Це третя базисна змінна.

Крок 3 (9). У 3-му рядку повністю задовольняється пропозиція, тому викреслюємо його.

Виконуючи далі кроки 1,2,3, отримуємо базисний початковий розв’язок, так як це показано на рис. 6. Стрілочками вказано послідовність, у якій знаходимо базисні змінні.