Транспортная задача. Базисное решение транспортной задачи

Тема: Транспортная задача. Базисное решение транспортной задачи.

Многие задачи экономико-математического моделирования являются оптими­зационными, т. е. в них требуется найти максимальное (минимальное или равное определенному числу) значение некоторой функции, называемой целевой, при заданных ограничениях на аргументы этой функции. Примерами таких задач могут быть определение условий максимальной прибыли при производстве продукции или составление плана перевозок с минимальными затратами. Реальные задачи имеют много условий, поэтому поиск оптимального решения требует большого объема вычислений. Использование ЭВМ позволяет производить сложные расчеты за короткий срок.

Широкий класс экономических задач приводит к поиску оптимального значения целевой функции, которая представляет собой линейную функцию нескольких переменных. К этому классу относится транспортная задача. Многие задачи, не являющиеся транспортными по физическому смыслу, в математической модели подобны им. Таковы, например, задачи оптимального распределения финансов, кредитов, производства между предприятиями, посевных площадей, задачи о назначениях, закреплении механизмов за видами работ и др. Решение транспортной задачи является основой решения всех перечисленных задач.
Транспортная задача формулируется следующим образом: имеется т пунктов поставки и п пунктов потребления некоторого продукта. Для каждого пункта поставки задан имеющийся запас А_т продукта, а для каждого пункта потребности задан объем В_n потребностей. Известна также стоимость перевозки с_тп (тариф) из каждого пункта поставки в каждый пункт потребления единицы продукта. Требуется составить план перевозок с минимальной стоимостью.
Транспортная задача, в которой сумма запасов равна сумме потребностей, т. е. ΣА_m = ΣB_n называется задачей с закрытой моделью. Если же это равенство не выполняется, то говорят, что задача имеет открытую модель.
Стоимость перевозки от т-го поставщика к n-му потребителю равна произведению x_mn·c_mn, где x_mn - перевозимое количество продукта.
Стоимость всех перевозок равна сумме стоимостей всех частичных перевозок Σx_mn·c_mn, эту сумму и принимают за целевую функцию, для которой требуется найти минимальное значение.

В табличной форме эта задача выглядит так:

Поставщики	Потребители				Запасы
	B1	B2	B3	B4
А1	6	2	1	3		75
А2	5	4	2	5		30
A3	1	3	7	8		55
Потребность	50	30	24	56