Транспортная задача

 

Далее, используя полученные значения потенциалов, для каждой свободной переменной вычисляем оценки dij по формуле:

dij = cij + ui + vj .

Результаты заносим в матрицу оценок (dij), проставив в клетках базисных переменных прочерки:

.

Так как в матрице оценок есть отрицательный элемент d12 = – 5, то опорный план неоптимальный. Для получения нового плана необходимо свободную переменную x12 перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (1;2) цикл пересчёта.

Цикл пересчёта – это ломаная линия, вершины которой расположены в занятых клетках таблицы поставок (кроме одной, предназначенной для заполнения), а звенья – вдоль строк и столбцов, причём в каждой вершине цикла встречается лишь два звена, одно из которых находится в строке, а другое – в столбце, и в каждых строке и столбце чётное число вершин. Перемещение по циклу производится по следующим правилам:

– каждой из вершин, связанной циклом с данной свободной клеткой, приписывают определённый знак, причём свободной клетке соответствует знак «+», а далее – поочерёдно то «–», то «+»;

– в данную свободную клетку переносится меньшее из значений xij, стоящих в клетках со знаком «–», а соответствующая переменная xij становится свободной. Одновременно это число добавляется ко всем значениям xij, стоящим в клетках со знаком «+», и вычитается из всех значений xij, стоящих в клетках со знаком «–».

В данном случае цикл пересчёта и перемещение по циклу представлены в таблице 12.

 

Таблица 12-Таблица метода наименьших затрат

ПО	ПН										ui
	В1		В2		В3		В4		В5
А1	30				15				5		0
		7	+	6		8		10	-	12
А2			20				20		20		-6
		9	-	5		7		4	+	6
А3					40						-4
		6		8		4		9		7
vj	7		11		8		10		12

 

В результате получаем новый план, F1 = 210+30+75+120+160+80+150=825 (см. таблица 13).

Таблица 13-Таблица метода наименьших затрат

ПО	ПН										ui
	В1		В2		В3		В4		В5
А1	30		5		15						0
		7		6		8		10		12
А2			15				20		25		-1
		9		5		7		4		6
А3					40						-4
		6		8		4		9		7
vj	7		6		8		5		7

 

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции  F* = 825.

Однако в матрице оценок присутствует элемент d15 = 0, что говорит о том, что оптимальный план единственный. Для получения нового оптимального плана необходимо свободную переменную x15 перевести в базис. Чтобы определить, какую переменную нужно вывести из базиса, строим для клетки (1;5) цикл пересчёта в таблице 14 по сформулированным выше правилам.

 

Таблица 14-Таблица метода наименьших затрат

ПО	ПН										ui
	В1		В2		В3		В4		В5
А1	30		5	+	15					-	0
		7		6		8		10		12
А2			15	-			20		25	+	-1
		9		5		7		4		6
А3					40						-4
		6		8		4		9		7
vj	7		6		8		5		7

 

 В свободные переменные переходит любая из переменных x32 или x24, например, x24, при этом в клетку (3;2) отправляем фиктивную поставку (таблица 15), то есть x32 = 0 (если не сделать этого, число базисных переменных станет равным шести, а не семи, как должно быть в данной задаче). В результате получаем новый план, F2 = 210+30+75+120+160+80+150=825  .

 

Таблица 15-Таблица метода наименьших затрат

ПО	ПН										ui
	В1		В2		В3		В4		В5
А1	30		5		15						0
		7		6		8		10		12
А2			15				20		25		-1
		9		5		7		4		6
А3					40						-4
		6		8		4		9		7
vj	7		6		8		5		7

Вычислим значения потенциалов для полученного плана:

и составим матрицу оценок:

.

Так как в матрице оценок нет отрицательных элементов, то полученный план:

оптимальный, и минимальное значение целевой функции  F* = 825.

Однако, продолжив решение, получаем предыдущий план (предлагаем убедиться самостоятельно).

 

Ответ:

, ;

F* = 825.

 

 

 

 

 

 

ЗАКЛЮЧЕНИЕ

 

 Математическими методами составили оптимальный план. Решение исходной задачи линейного программирования графическим методом: max f(x) =390  и достигается при выпуска продукции Ⅰ вида равному 6 и выпуска продукции  Ⅱ вида равному 5.

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Когда суммарный объём предложений не равен общему объёму спроса на товары запрашиваемые пунктами.

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

Получены следующие результаты:

1. Метод северо-западного угла: 1045 рублей
2. Метод наименьшего элемента: 850 рублей
3. Метод аппроксимации Фогеля: 850 рублей

Оптимизируя план, полученный методом наименьшего элемента, достигнут результат равный 825-это оптимальный результат.

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. Ермаков, В.И. Общий курс высшей математики для экономистов: учебное пособие/  В.И. Ермаков - М: Инфра-М. 2005- 245 с.
2. Кузнецов, А.В. Высшая математика. Математическое программирование: учебное пособие/ А.В.  Кузнецов, В.А Сакович., Н.И Холод -  М.: Высшая школа 2008 – 353 с.
3. Красс, М.С. Основы математики и ее приложения в экономическом образовании: учебное пособие/ М.С  Кузнецов, Б.П., М. И. Чупрынов.- М: Дело, 2006 – 307 с.
4. Зубов, М.И. Общий курс высшей математики: учебное пособие/  А.Н. Ермолов - М: Инфра-М. 2005- 255 с.
5. Коваленко, И.М. Высшая математика. Математическое программирование: учебное пособие/ И.М.  Коваленко, В.А Симонов., Н.И Холод -  М.: Высшая школа 2009 – 363 с.