Транспортная задача линейного программирования

ТЕМА 2 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ТЗ)

2.1 Математическая модель транспортной задачи

У m поставщиков [pic 1] сосредоточен однородный груз в объемах [pic 2] единиц, соответственно. Данный груз необходимо доставить потребителям [pic 3], спрос которых выражается величинами [pic 4] единиц, соответственно. Известна стоимость [pic 5] перевозки единицы груза (тариф) из [pic 6]-го ([pic 7]) поставщика [pic 8]-му ([pic 9]) потребителю.

Требуется составить план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всего груза минимальны.

Для наглядности, условие транспортной задачи можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (таблица 2.1).

Таблица 2.1

Составим математическую модель ТЗ.

Введем переменные [pic 33] – объемы перевозок от [pic 34]-го поставщика [pic 35]-му потребителю.

Матрицу [pic 36] будем называть матрицей перевозок.

Цель ТЗ – минимизировать суммарные затраты на перевозку всего груза, следовательно, целевая функция будет иметь вид:

[pic 37]        (2.1)

Составим систему ограничений (2.2) в случае, когда [pic 38], которая будет определять ОДР данной задачи.

[pic 39]                                         (2.2)

Первые m уравнений системы (2.2) – это ограничения на запас груза  у поставщиков, следующие n уравнений системы (2.2) – это ограничения на запросы потребителей в грузе, неравенства системы – это ограничения на экономический смысл переменных (объем груза не может быть отрицательным).

Будем называть план перевозок

[pic 40]

допустимым, если он удовлетворяет системе ограничений (2.2).

Допустимый план перевозок, доставляющий минимум целевой функции, называется оптимальным.

Закрытая и открытая модели транспортной задачи

Модель ТЗ называют закрытой (сбалансированной), если суммарный объем груза всех поставщиков, равен суммарному спросу потребителей, т.е. выполняется равенство:

[pic 41].                        (2.3)

Если для транспортной задачи выполняется одно из условий:

[pic 42],                (2.4)