МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Реферат
по дисциплине: Методы и модели в экономике и менеджменте.
на тему: «Применение методов линейного программирования для оптимизации стоимости перевозок»
Воронеж 2010
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с

баз

потребителям

.
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим количество груза, имеющегося на каждой из
баз (запасы), соответственно
,а общее количество имеющегося в наличии груза–
:
; заказы каждого из потребителей (потребности) обозначим соответственно
, а общее количество потребностей –
:
,
Тогда при условии 
мы имеем закрытую модель, а при условии 
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза
, либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены
.Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (Таблица 3. ):
Таблица 3. - План перевозок с указанием запасов и потребностей
Условие
или
означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное
означает количество груза, перевозимого с базы
потребителю
: совокупность этих величин образует матрицу (матрицу перевозок).Очевидно, переменные
должны удовлетворять условиям:

Система (3. ) содержит
уравнений с
неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (3. ) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (3. ) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.Такая структура системы (3. ) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием
,
.Перепишем систему (3. ) в виде

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