fy"> 13 12 71475 30A 2 11 15 8 33 1268 48A 3 610 9 10 11 811 20A < span align = "justify"> 4 14810 15 10 15 15 30Заявкі b j 1827422615128
Складемо опорний план. Можна застосувати метод В«північно-західного вугілляВ». Нехай пункт В 1 подав заявки на 18 одиниць вантажу. Задовольнимо її із запасів А 1 . Після цього в ньому залишається ще 30-18 = 12 одиниць вантажу. Віддамо їх пункту В 2 . Але заявка цього пункту ще не задоволена. Виділимо залишок 27-12 із запасів А 2 і т.д. розмірковуючи аналогічним чином, складемо таблицю 4.3 . Отриманий план перевезень є опорним, але навряд чи він є оптимальним в сенсі вартості перевезень.
Нагадаємо, що пряма , яка має з областю, принаймні, одну спільну точку, до того ж так, що вся область лежить по одну сторону від цієї прямої, називається опорної по відношенню до цієї області.
Таким чином, завдання ЛП на геометричному мовою може бути сформульована так: серед прямих рівня функції мети? знайти опорну по відношенню до ОДР і притому так, щоб вся область лежала з боку великих значень?. Наш план - не оптимальний. Відразу видно, що його можна поліпшити, якщо провести в ньому В«циклічну перестановкуВ», зменшивши перевезення в В«дорогоюВ» клітці (2.3) з вартістю 12. але зате, збільшивши перевезення в В«дешевоїВ» клітці (2.4) з вартістю 6. щоб план залишався опорним, ми повинні при цьому зробити одну з вільних клітин базисної, а одну з базисних - вільною.
Скільки одиниць вантажу можемо ми перенести по циклу наступного циклу: (2.4)? (3.4)? (3.3)? (2.3) , збільшуючи перевезення в непарних вершинах циклу і зменшуючи в парних? Вочевидь, не більше 11 одиниць (інакше перевез...
