Оптимальные экономико-математические модели

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

Размещено на

19. (Транспортная задача)

Имеется пять поставщиков однородной продукции с объемами поставок и пять потребителей с объемами потребления .

Решить транспортную задачу

Исходная матрица планирования

Матрица планирования
	5	17	9	7	11
	6	7	6	10	6
	9	7	9	6	12
	8	10	14	7	7
	11	8	9	11	5

Решение

Так как

и

(т.е. ), то исходная транспортная задача является закрытой.

Найдем начальный опорный план методом минимальной стоимости, а затем оптимизируем его методом потенциалов.



1. Построение начального опорного плана

Из таблицы стоимостей выберем наименьшую стоимость

.

Заполним клетку (1,1)

.

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

Заполним клетку (5, 5)

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

В оставшейся таблице стоимостей наименьшей является стоимость

.

Заполним клетку (2, 3)

.

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

Заполним клетку (3, 4)

.

В клетку (3, 4) помещаем 200 ед.груза и исключаем из дальнейшего рассмотрения третью строку (запасы поставщика полностью израсходованы).

В оставшейся таблице стоимостей наименьшей является стоимость

Заполним клетку (1, 4)

.

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

Заполним клетку (2, 2)

.

В клетку (2, 2) помещаем 10 ед.груза и исключаем из дальнейшего рассмотрения вторую строку (запасы поставщика полностью израсходованы).

В оставшейся таблице стоимостей наименьшей является стоимость



Заполним клетку (5,2)

.

20 ед.груза помещаем в клетку (5, 2), тем самым полностью расходуя запасы поставщика .

В оставшейся таблице стоимостей наименьшей является стоимость

Заполним клетку (4, 2)

.

110 ед.груза помещаем в клетку (4, 2), тем самым полностью расходуя запасы поставщика .

Заполним клетку (1, 2)

.

70 ед.груза помещаем в клетку (1, 2), тем самым полностью израсходовав запасы поставщика и полностью удовлетворив потребности потребителя .

В результате получаем план



Матрица планирования
	5120	1770	9	790	11
	6	710	6280	10	6
	9	7	9	6200	12
	8	10110	14	7	7
	11	820	9	11	5100

Определим стоимость плана

2. Метод потенциалов

Построим систему потенциалов. Положим . Найдем остальные потенциалы по формулам: .

Матрица планирования
	5 120	- 17 70	9	+ 7 90	11
	6	7 10	6 280	10	6
	9	+ 7 х	9	- 6 200	12
	8	10 110	14	7	7
	11	8 20	9	11	5 100
						7130

По найденной системе потенциалов вычислим оценки незанятых клеток по формуле:

Условия оптимальности () нарушаются в клетках (1, 3), (1, 5), (3, 2), (3, 3), (3, 5). Поэтому найденный опорный план не является оптимальным. Следовательно, одна из этих клеток должна быть загружена некоторым объемом поставок. В первую очередь заполняется та клетка, для которой достигается максимум среди : . Значит, включим переменную в число базисных. Пометим ее знаком «х» и построим цикл, который начинается и заканчивается в этой клетке (3, 2), а вершины цикла располагаются в занятых клетках.

(3, 2) - (3, 4) - (1, 4) - (1, 2).

Клетка (3, 2) помечается знаком «+», затем клетки, находящиеся в вершинах цикла отмечаются чередующимися знаками «-» и «+». Величина поставок, перемещаемая в клетку (3, 2), равна минимуму из поставок со знаком «-», т.е.

.

Величина вычитается из объемов поставок клеток со знаком «-» и прибавляется к объемам поставок клеток со знаком «+». В результате получаем новый опорный план, затраты на реализацию которого составляют

поставка опорный план потребитель



Матрица планирования
	5 120	17	9	7 160	11
	6	7 10	6 280	10	6
	9	+ 7 70	9	- 6 130	12
	8	- 10 110	14	+ 7 х	7<... Другие файлы: Оптимальные методы в совершенствовании планирования и управления производством Содержание и построение экономико-математических методов. Роль оптимальных методов в планировании и управлении производством. Экономико-математические... Экономико-математические методы и модели В учебном пособии рассматриваются основные экономико-математические методы и модели, а также специальные модели, предложенные авторами. В качестве при... Экономико-математические методы и прикладные модели Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственн... Экономико-математические модели Основные понятия и типы моделей, их классификация и цели создания. Особенности применяемых экономико-математических методов. Общая характеристика осно... Экономико-математические методы и модели в управлении производством Учебное пособие содержит материал для изучения, исследования экономических процессов, их протекания в современных условиях, установления устойчивых те...