Решение задач линейного программирования транспортной задачей (стр. 2 из 4)

Этот метод состоит из шагов:

1) Сделать начальное распределение(интуитивный подход), проверить матрицу на полноценность, в случаенеобходимости провести корректировку.

2) Получить номер индекса для каждойстроки и столбца. Делая это используя только заполненные ячейки. Всегда есть покрайней мере одна заполненная ячейка в каждом столбце и строке.

а) начинаем, назначая ноль в первойстроке

б) определить индекс столбца длялюбой заполненной ячейки в строке 1, используя следующие соотношения:

индекс столбца = U;

индекс строки = V;

затраты ячейки = С;

U = C-V

в) Каждое новое значение столбцапозволит вычислить по крайней мере 1 новое значение строки и наоборот.Продолжайте эту процедуру пока все строки и столбцы будут заполнены индексами.

3) Получить оценки для пустых ячеек

W – оценка ячейки

W = C- (U+V)

1 – C: W = 7-(0+9) = -2

2 – A: W = 4-(1+3)= 0

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

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

 

2. Содержательная постановка задачи

Частным случаем задачи линейногопрограммирования является транспортная задача. Проблема транспортировкивключает поиск низко затратных схем распределения товарных запасов от многихисточников до многих мест назначения.

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

Информация необходимая дляиспользования модели включает следущее:

- список отправных пунктов ипропускная способность каждого (количество поставок за определенный период);

- список мест назначения и ихпоказатели спроса;

- стоимость транспортировки единицыпродукции от каждого отправленного пункта до каждого места назначения. Этаинформация сводится в транспортную таблицу.

 

 

3. Математическая постановка задачи

Пусть X_ij - количество груза перевозимого изпункта i в пункт j.

А1=40; А2=50; В1=20; В2=30; В3=40;

3 5 7

С = 4 6 10

Таблица 5

Начальные параметры

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

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

Ограничение по запасам:

Х₁₁ + Х₁₂ + Х₁₃<= 40

Х₂₁ + Х₂₂ + Х₂₃<= 50

X_ij>=0

Ограничение по спросу:

Х₁₁ + Х₂₁ <=20

Х₁₂ + Х₂₂ <=30

Х₁₃ + Х₂₃ <=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