Контрольная работа по предмету "Экономико-математическое моделирование"

Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x2), выполнив соответствующие этапы алгоритма.

После преобразований получаем новую таблицу:

 

Базис	B	x1	x2	x3	x4	x5
x3	81/2	0	11/2	1	-1/2	0
x1	21/2	1	1/2	0	1/2	0
x5	111/2	0	21/2	0	-1/2	1
F(X )	10	0	0	0	2	0

 

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

Значение 2 в столбце x4 означает, что теневая цена (двойственная оценка) равна 2.

 

 

 

 

 

 

 

 

 

 

 

4 Задача № 3

 

 Необходимо решить транспортную задачу: минимизировать расходы на доставку продукции заказчикам со складов фирмы, учитывая следующие затраты на доставку одной единицы продукции, объём заказа и количество продукции, хранящейся на каждом складе. Тарифы на перевозку единицы продукции, объёмы запасов продукции на складах, а также объёмы заказанной продукции представлены в таблице 33.

 

Таблица 33 – Исходные данные к задаче

Склад	Магазин				Запасы продукции на складе, ед.
	«Тверь»	«Рязань»	«Тула»	«Чехов»
Москва	15	7	11	4	1000
Санкт-Петербург	6	4	12	8	550
Саратов	7	11	5	10	3200
Объём заказа продукции, ед.	1000	550	500	2700	4750

 

 

Математическая модель транспортной задачи:

F = ∑∑cijxij,    (1)

при условиях:

∑xij = ai,  i = 1,2,…, m,   (2)

∑xij = bj,  j = 1,2,…, n,   (3)

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	4	Запасы
1	15	7	11	4	1000
2	6	4	12	8	550
3	7	11	5	10	3200
Потребности	1000	550	500	2700

 

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 1000 + 550 + 3200 = 4750

∑b = 1000 + 550 + 500 + 2700 = 4750

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

Занесем исходные данные в распределительную таблицу.

	1	2	3	4	Запасы
1	15	7	11	4	1000
2	6	4	12	8	550
3	7	11	5	10	3200
Потребности	1000	550	500	2700

 

Этап I. Поиск первого опорного плана.

1. Используя метод наименьшей  стоимости, построим первый опорный  план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.

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

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

Искомый элемент равен 4

Для этого элемента запасы равны 1000, потребности 2700. Поскольку минимальным является 1000, то вычитаем его.

x14 = min(1000,2700) = 1000.

 

x	x	x	4	1000 - 1000 = 0
6	4	12	8	550
7	11	5	10	3200
1000	550	500	2700 - 1000 = 1700	0

 

Искомый элемент равен 4

Для этого элемента запасы равны 550, потребности 550. Поскольку минимальным является 550, то вычитаем его.

x22 = min(550,550) = 550.

 

x	x	x	4	0
x	4	x	x	550 - 550 = 0
7	x	5	10	3200
1000	550 - 550 = 0	500	1700	0

 

Искомый элемент равен 5

Для этого элемента запасы равны 3200, потребности 500. Поскольку минимальным является 500, то вычитаем его.

x33 = min(3200,500) = 500.

 

x	x	x	4	0
x	4	x	x	0
7	x	5	10	3200 - 500 = 2700
1000	0	500 - 500 = 0	1700	0

 

Искомый элемент равен 7

Для этого элемента запасы равны 2700, потребности 1000. Поскольку минимальным является 1000, то вычитаем его.

x31 = min(2700,1000) = 1000.

x	x	x	4	0
x	4	x	x	0
7	x	5	10	2700 - 1000 = 1700
1000 - 1000 = 0	0	0	1700	0

 

 Искомый элемент равен 10

Для этого элемента запасы равны 1700, потребности 1700. Поскольку минимальным является 1700, то вычитаем его.

x34 = min(1700,1700) = 1700.

x	x	x	4	0
x	4	x	x	0
7	x	5	10	1700 - 1700 = 0
0	0	0	1700 - 1700 = 0	0

 

	1	2	3	4	Запасы
1	15	7	11	4[1000]	1000
2	6	4[550]	12	8	550
3	7[1000]	11	5[500]	10[1700]	3200
Потребности	1000	550	500	2700

 

2. Подсчитаем число занятых клеток  таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является  вырожденным. 

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 4*1000 + 4*550 + 7*1000 + 5*500 + 10*1700  = 32700

Искомый элемент равен 4

Для этого элемента запасы равны 550, потребности 550. Поскольку минимальным является 550, то вычитаем его.

x22 = min(550,550) = 550.

 

15	x	11	4	1000
x	4	x	x	550 - 550 = 0
7	x	5	10	3200
1000	550 - 550 = 0	500	2700	0

 

Искомый элемент равен 4