Граф-схема решения задачи линейного программирования

Первая модель решения: на полном двудольном графе отношений.

Задача имеет очевидное решение, вытекающее из метода минимума транспортных расходов. Решение представлено на рис. 1.1.

Принято по дуге графа (А, 1) при С_А1=2 транспортировать 200 тонн и платить 2*200=400 усл. ед. стоимости.

Остаток бетона 320–200=120 отправляется на строку 2 при затратах на транспортировку 4*120=480 усл. ед. На стройку 3 по 6 усл. ед. за тонну его отправлять не выгодно.

А налогично имеем дугу (В, 3) с минимальными затратами 3*220=660 усл. ед. Остаток по дуге (В, 2) с неизбежными затратами 5*160=800 усл. ед.

Общая стоимость суточных затрат составит 2340 усл. ед. из единственности приведенного решения вытекает и его оптимальность.

Очевидность подобного утверждения можно показать с помощью спора моделей.

В данном случае под спором моделей понимается получение одинакового результата из разных моделей (методов) решения задач.

Для этого вместо топологии решения на графе сведем решение задачи к топологии метрического пространства с метрикой по Евклиду.

Другими словами, построим модели алгебраического вида и дадим их интерпретацию в двухмерном евклидовом пространстве.