Взять любой опорный план перевозок, в котором отмечены m +n - 1 базисных клеток (остальные клетки свободные)

1. Взять любой опорный план перевозок, в котором отмечены m +n - 1 базисных клеток (остальные клетки свободные).

2. Определить для этого плана платежи (a_i и b_j) исходя из условия, чтобы в любой базисной клеткепсевдостоимости были равны стоимостям. Один из платежей можно назначитьпроизвольно, например, положить равным нулю.

3. Подсчитать псевдостоимости č_i,j = a_i + b_j для всех свободных клеток. Если окажется, что все они не превышают стоимостей, то план оптимален.

4. Если хотя бы в одной свободной клетке псевдостоимость превышает стоимость, следует приступить к улучшению плана путём переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости).

5. После этого заново подсчитываются платежи и псевдостоимости, и, если план ещё не оптимален, процедура улучшения продолжается до тех пор, пока не будет найден оптимальный план. Так в нашем примере после 2 циклов расчетов получим оптимальный план. При этом стоимость всей перевозки изменялась следующим образом: F₀ = 723, F₁ = 709, F₂ = F_min = 703.

Следует отметить так же, что оптимальный план может иметь и другой вид, но его стоимость останется такой же F_min = 703.

Составьте оптимальный план перевозки угля с минимальными транспортными расходами с шахт Варгашорская (В), Западная (З) и Комсомольская (К), еженедельно добывающих соответственно 26,32 и 17тыс. т. Покупатели угля расположены в разных городах В, В, С и D, заявки которых составляют 28, 19, 12 и 16 тыс. т между поставщиками и потребителями представлены транспортной таблицей.

Шахты	Потребители				Добыча угля, тыс. тонн в неделю
	A	B	C	D
Западная	70	76	72	68	32
Варгашорская	80	84	82	77	26
Комсомольская	80	83	82	76	17
Заявки, тыс. тонн	28	19	12	16

Решение:

Математическая модель данной задачи имеет вид:

F = 70х₁₁+76х₁₂+72х₁₃+68х₁₄+80х₂₁+84х₂₂ +82х₂₃+77х₂₄+80х₉+83х₁₀ +82х₁₁+76х₁₂ →min

Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рисунке:

При введении зависимостей лист MS Excel в режиме просмотра формул имеет вид:

После отражения закономерностей экранная форма принимает вид:

Окно "Поиск решения" после ввода всех необходимых данных задачи имеет следующий вид:

Оптимальное решение задачи в экранной форме имеет вид:

 

Минимальные транспортные расходы на перевозку угля равны 5715.

Заключение

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

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность; решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.

Список используемой литературы

1.  Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976 г.

2.  Карманов В.Г. Математическое программирование. - М.; Наука, 1986г.

3.  Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 1978г.

4.  Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 1979г.

5.  Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука, 1986г