Транспортная задача линейного программирования

∆₁₂ = 0+0-1=(-1)

∆₁₃ = 0+7-8=(-1)

∆₁₄ = 0-3-12=(-15)

∆₂₃ = 3+7-7=3

∆₂₄ = -3+3-5=(-5)

∆₃₁ = 2+7-3=6

Мы получили положительные  и отрицательные потенциалы. Если есть положительный потенциал, то коэффициент  F можно улучшить (уменьшить). Если положительных потенциалов не останется, задача решена верно и коэффициент F уменьшить уже нельзя. Поскольку у нас положительные коэффициенты, выберем из них самый максимальный.

Вернёмся к самой таблице  и возьмём выбранную нами клетку как 1 из вершин прямоугольника. Теперь перед нами стоит задача: составить  прямоугольник, у которого 3 вершины  будут являться заполненными клетками, но наша 1 выбранная вершина будет, как очевидно, принадлежать пустой клетке. Согласно их физическому расположению, вырисуем для удобства этот прямоугольник и вынесем на его вершины значения выбранных клеток. Присвоим вершине со значением 0 и вершине, противоположной вершине со значением 0 – знак «+», что означает, что вершины положительные, а остальным вершинам знак «-», что значит вершины отрицательные, т. е. получится вот так:

 

50				80
	-		+
	+		-
0				40

 

 Среди 2 отрицательных  вершин находим наименьшее число.  В данном примере это число  40. Теперь к положительным вершинам прибавляем это число, а из отрицательных - отнимаем. Получится так:

 

50-40				80+40
	-		+
	+		-
0+40				40-40

 

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

 

Шаг 2.

Опираясь на полученные значения из предыдущего шага, необходимо составить  новое распределение.

Составим таблицу, расставим  тарифы и сделаем распределение:

 

Ai	Bj	b1		b2		b3		b4		Ui
		150		120		80		50
a1	100	2	100	1		8		12		0
a2	130	5		3	120	7	10	5		2
a3	170	3	50	7		14	70	4	50	1
Vg			2	1			5		3

Таблица 4

 

Найдём коэффициент F:

F = 2*100+3*120+7*10+3*50+14*70+4*50=1960 единиц.

Находим потенциалы занятых  клеток. Их я уже вписал в таблицу  сразу.

 

 

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₂ = 0+0-1=(-1)

∆₁₃ = 13+0-8=5

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+3-5 =0

∆₂₄ =3+3-5=1

∆₃₂ = 0+1-7=(-6)

Положительное значение у  клетки (1;3) – с ним и станем производить цикл.

Составим цикл и произведём над ним действия перераспределения, то есть найдём минимальное отрицательное  и, соответствуя знакам, сделать простые  математические действия.

100-70				0+70
	-		+
	+		-
50+70				70-70

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

 

Шаг 3.

Опираясь на полученные значения из предыдущего шага, необходимо составить  новое распределение.

Составим таблицу, расставим  тарифы и сделаем распределение:

 

Ai	Bj	b1		b2		b3		b4		Ui
		150		120		80		50
a1	100	2	30	1		8	70	12		0
a2	130	5		3	120	7	10	5		-1
a3	170	3	120	7		14		4	50	1
Vg			2	4			8		3

Таблица 5

 

Найдём коэффициент F:

F = 2*30+3*120+8*70+3*120+7*10+3*120+4*50=1610 единиц.

Находим потенциалы занятых  клеток. Их я уже вписал в таблицу  сразу.

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₂ = 4+0-1=3

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+(-1)-5=(-4)

∆₂₄ = 3+(-1)-5=(-3)

∆₃₂ =4+1-7=(-2)

∆₃₃ = 8+1-14=(-5)

Положительное значение у  клетки (1;2) – с ним и станем производить цикл.

Составим цикл и произведём над ним действия перераспределения, то есть найдём минимальное отрицательное  и, соответствуя знакам, сделать простые  математические действия.

0+70				70-70
	+		-
	-		+
120				10+70

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

 

Шаг 4.

Опираясь на полученные значения из предыдущего шага, необходимо составить  новое распределение.

Составим таблицу, расставим  тарифы и сделаем распределение:

 

Ai	Bj	b1		b2		b3		b4		Ui
		150		120		80		50
a1	100	2	30	1	70	8		12		0
a2	130	5		3	50	7	80	5		2
a3	170	3	120	7		14		4	50	1
Vg			2	1			5		3

Таблица 6

 

Найдём коэффициент F:

F = 2*30+1*70+3*50+7*80+3*120+4*50=1400 единиц.

Находим потенциалы занятых  клеток. Их я уже вписал в таблицу  сразу.

Теперь выясним оптимальность  этого решения, оценив свободные  клетки.

∆₁₃ = 5+0-8=(-3)

∆₁₄ = 3+0-12=(-9)

∆₂₁ = 2+2-5=(-1)

∆₂₄ = 3+2-5=0

∆₃₂ =1+1-7=(-5)

∆₃₃ = 5+1-14=(-8)

Положительных чисел нет, мы нашли оптимальное решение  этой задачи.

2.2 Экономический вывод задачи

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

На целых 39% снизили стоимость перевозки:

1. Потребителю b1, потребовалось взять 30 единиц сырья со склада a1 и 120 единиц сырья со склада a3;
2. Потребителю b2, потребовалось взять 70 единиц сырья со склада a1 и 50 единиц сырья со склада a2;
3. Потребителю b3, потребовалось взять 80 единиц сырья со склада a2;
4. Потребителю b4, потребовалось взять 50 единиц сырья со склада a3.

 

ЗАКЛЮЧЕНИЕ

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

 

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Апатенок Р.Ф. Математика для экономистов. М, Просвещение, 2004.
2. Баумоль. У. Экономическая теория и исследование операций. – М.; Наука, 2004.
3. Большев Л.Н., Смирнов Н.В. Таблицы математической статистики. М.: Наука, 2004.
4. Боровков А.А. Математическая статистика. М.: Наука, 2004.
5. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. – М.: Высшая школа, 2004.