Глава 2. Транспортная задача линейного программирования (тз)

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

У m поставщиков сосредоточен однородный груз в объемахединиц, соответственно. Данный груз необходимо доставить потребителям, спрос которых выражается величинамиединиц, соответственно. Известна стоимостьперевозки единицы груза (тариф) из-го () поставщика-му () потребителю.

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

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

Таблица 2.1

	Потребители								Запас , единиц
Поставщики					...
					...
					...
...									...
	...		...		...		...
					...
Потребность ,единиц					...

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

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

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

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

(2.1)

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

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

(2.2)

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

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

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