МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ВОРОНЕЖСКИЙ ИНСТИТУТ ВЫСОКИХ ТЕХНОЛОГИЙ

Факультет заочно-послевузовского обучения

КУРСОВАЯ РАБОТА

По дисциплине: "Методы оптимизации"

На тему: " Решение задач транспортного типа методом потенциалов "

Воронеж 2003 г.

СОДЕРЖАНИЕ

1. Линейная транспортная задача. 3
2. Математическая модель транспортной задачи. 4
3. Составление опорного плана. 5
4. Распределительный метод достижения оптимального плана. 8
5. Решение транспортной задачи методом потенциалов. 11
Список использованной литературы 16

1. Линейная транспортная задача.

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С i j.

Далее, предполагается, что

[pic] где ai есть количество продукции, находящееся на складе i, и bj – потребность потребителя j.

Замечание.

1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок [pic]то количество продукции, равное [pic]остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью [pic] и положим транспортные расходы pi,n+1 равными 0 для всех i.

2. Если сумма поданных заявок превышает наличные запасы [pic]то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом [pic] и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

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

[pic]

[pic]

[pic]

[pic]

[pic]

где xij количество продукции, поставляемое со склада i потребителю j, а С i j издержки (стоимость перевозок со склада i потребителю j).

3. Составление опорного плана.

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ северо- западного угла, способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.