Методы решения линейных оптимизационных моделей

1. «Методы решения линейных оптимизационных моделей»

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

[pic 1]

[pic 2]

[pic 3]

Выполним построение прямых и определим полуплоскости:

[pic 4]

[pic 5]

[pic 6]

[pic 7]

[pic 8]

[pic 9]

Результаты построения с обозначенными границами многоугольника решений представлены на рисунке.

[pic 10]

Выполним построение вектора по коэффициентам целевой функции и обозначим вершины многоугольника.

[pic 11]

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

Такими точками являются точки A и B (в виду того, что прямая целевой функции параллельна прямой ).[pic 12]

Точка A образована при пересечении прямых  и . Вычислим координаты точки пересечения, решив систему уравнений:[pic 13][pic 14]

[pic 15]

Получим:

[pic 16]

[pic 17]

Минимальное значение целевой функции равно:

[pic 18]

Точка B – точка пересечения прямых  и .[pic 19][pic 20]

Вычислим координаты точки пересечения, решив систему уравнений:

[pic 21]

Получим:

[pic 22]

[pic 23]

Минимальное значение целевой функции равно:

[pic 24]

1. Транспортные задачи

На складах хранится мука, которую необходимо завезти в хлебопекарни. Номера складов и номера хлебопекарен выбираются в соответствии с вариантами табл. 1. Текущие тарифы перевозки муки [руб./т], ежемесячные запасы муки [т/мес.] на складах и потребности хлебопекарен в муке [т/мес.] указаны в табл. 2.

При этом необходимо учитывать, что из-за ремонтных работ временно нет возможности перевозить муку с некоторых складов в некоторые хлебопекарни. В табл. 1 это показано в графе «Запрет перевозки» в формате № склада x № хлебопекарни. Например, «2x3» обозначает, что нельзя перевозить муку со склада № 2 в хлебопекарню № 3.

Кроме того, необходимо учесть, что некоторые хлебопекарни имеют договоры на гарантированную поставку муки с определенных складов. В табл. 1. это показано в графе «Гарантированная поставка» в формате № склада x № хлебопекарни = объем поставки. Например, «1x4=40» обозначает, что между складом № 1 и магазином № 4 заключен договор на обязательную поставку 40 т муки.

[pic 25]

[pic 26]

Решение:

        Выпишем исходные данные в таблицу:

        Исключим перевозку со склада № 2 в хлебопекарню № 2, а также со склада № 3 в хлебопекарню № 4. Для этого установим цену выше остальных – 900 руб./т.

        Далее, учтём то, что между складом № 3 и магазином № 3 заключен договор на обязательную поставку 50 т муки.

        Вычтем их из спроса и запаса, а далее учтём в функции затрат: