Курсовая работа: Решение задач линейного программирования транспортной задачей

Х₁₃ + Х₂₃ <= 40

Этапы решения транспортной задачи:

1)  Получение начального решения

2)  Проверка решений на оптимальность

3)  Усовершенствование несовершенных решений

Интуитивный подход.

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

Таблица 6

Заполнение ячеек

	B1		B2		B3
A1		3		5		7
	20		20				40
A2		4		6		10	50
			10		40
	20		30		40

Целевая функция:

Z=3*20+5*20+6*10+10*40=60+100+60+400=620

4. Решение задачи

 

4.1 Математическое решение задачи

Условие задачи:

Три предприятия данного экономического района могут производить однородную продукцию, в количествах соответственно равных А1, А2 и А3 единиц. Эта продукция должна быть поставлена 5-и потребителям в количествах, соответственно равных В1, В2, В3, В4 и В5 единиц. Затраты связанные с производством и доставкой продукции, задаются матрицей С.

А1=180; А2=350; А3=20

В1=110; В2=90; В3=120; В4=80; В5=150

Таблица 7

Индексы матрицы

	В1	В2	В3	В4	В5
А1	7	12	4	6	5
А2	1	8	6	5	3
А3	6	13	8	7	4

Таблица 8

Первоначальное заполнение ячеек

	7		12		4		6		5	180
110		70
	1		8		6		5		3	350
		20		120		80		130
	6		13		8		7		4	20
								20
110		90		120		80		150

Найдем целевую функцию:

Z=110*7+70*12+20*8+120*6+80*5+130*3+20*4=3360

 

Таблица 9

Первое оценивание ячеек

1-С			1-D			1-E			2-A
+4	-12		+6	-12		+5	-12		+1	-7
+8	-6		+8	-5		+8	-3		+12	-8
-6			-3			-2			0

3-A			3-B			3-C			3-D
+6	-7		+13	-8		+8	-6		+7	-5
+12	-8		+3	-4		+3	-4		+3	-4
+6	-5		+4			+1			+1
+3	-4
+3

Таблица 10

Редактирование таблицы от оцененной ячейки

	7		12		4		6		5	180
110				70
	1		8		6		5		3	350
		90		50		80		130
	6		13		8		7		4	20
								20
110		90		120		80		150