Реализация модифицированного симплекс-метода

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

2. Подсчитаем число занятых  клеток таблицы, их 6, а должно  быть m + n - 1 = 6. Следовательно, опорный  план является невырожденным.

Этап II. Улучшение опорного плана.

Проверим оптимальность  опорного плана. Найдем предварительные  потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=2	v2=-3	v3=3	v4=-4
u1=0	2[9]	5	8	1
u2=6	8[2]	3[7]	9[3]	2[4]
u3=3	7	4	6[5]	3

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 2*9 + 8*2 + 3*7 + 9*3 + 2*4 + 6*5  = 120

Все вычисления и комментарии  к полученным результатам доступны в расширенном режиме. Также приведено  решение двойственной транспортной задачи и анализ оптимального плана.

Заключение

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного  и выпуклого программирования М.; Наука, 1993 г.
2. Карманов В.Г. Математическое программирование. - М.; Наука, 2005г.
3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 2005г.
4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 2008г.
5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука, 1999г.
6. http://mathsemestr.ru