Математические методы и модели в экономике

 

Строку с базисом  х2 оставляем без изменения и слагаем соответствующий строк:

 

Б.П.	С	В	-1	-3	0	0	0	-M
			x1	x2	x3	x4	x5	z
x3	0	40	-1,4	0	1	0	0,6	-0,6
x4	0	120	2,4	0	0	1	0,4	-0,4
x2	-3	60	0,8	1	0	0	-0,2	0,2
F1		-180	-1,4	0	0	0	0,6	-0,6
f		0	0	0	0	0	0	1

 

Найденное решение М-задачи не является оптимальным. Так как и

, то  -генеральный элемент.

 

Б.П.	С	В	-1	-3	0	0	0	-M
			x1	x2	x3	x4	x5	z
x3	0	40	-1,4	0	1	0	0,6	-0,6
		70	1,4	0	0	0,583333	0,233333	-0,23333
x4	0	120	2,4	0	0	1	0,4	-0,4
x1	-1	50	1	0	0	0,416667	0,166667	-0,16667
x2	-3	60	0,8	1	0	0	-0,2	0,2
		-40	-0,8	0	0	-0,33333	-0,13333	0,133333
F1		-180	-1,4	0	0	0	0,6	-0,6
		70	1,4	0	0	0,583333	0,233333	-0,23333
f		0	0	0	0	0	0	1

 

Или

 

Б.П.	С	В	-1	-3	0	0	0	-M
			x1	x2	x3	x4	x5	z
x3	0	110	0	0	1	0,583333	0,833333	-0,83333
x1	-1	50	1	0	0	0,416667	0,166667	-0,16667
x2	-3	20	0	1	0	-0,33333	-0,33333	0,333333
F1		-110	0	0	0	0,583333	0,833333	-0,83333
fM		0	0	0	0	0	0	1

 

 

Поскольку все оценки неотрицательны, решение оптимально.

Ответ

Приведем графическое решение  данной задачи.

Для этого построим область решений  системы ограничений.

Область решения системы ограничений  является четырехугольник АВСD, вектор градиент целевой функции и линя уровня точка D является точкой пересечения второй (2) и третьей (3) прямых. Для определения ее координаты решаем систему уравнений

 Таким образом,  D(50;20) и

 

№ 53. Транспортная задача.

Из трех пунктов хранения (или  производства) требуется доставить  однородный груз в пять пунктов потребления. Количество груза  в каждом пункте отправления, объемы потребления , а также стоимости перевозки единицы груза из пункта отправления в пункт потребления указаны в таблице. Составить такой план перевозок при котором общая стоимость перевозок была бы минимальной.

 

Решение. Данные расположим в таблице

 

ai           bj	200	150	150	200	100
250	7	4	3	1	2
200	2	9	4	2	2
300	1	10	12	1	9

 

Решаем транспортную задачу с помощью  метода потенциалов.

1. Проверим, является ли данная задача закрытой.

 

Так как  задача открытая. Вводим «фиктивный» пункт поставщиков объемом в 800-750=50 ед. Стоимость перевозок в этот пункт принимает равным 0.

 

ai   bj	200	150	150	200	100
250	7	4	3	1	2
200	2	9	4	2	2
300	1	10	12	1	9
50	0	0	0	0	0

2.Находим первый план задачи методом, например, наименьшего элемента матрицы транспортных издержек (последняя строка при этом не принимаем во внимание, т.к. он связан с фиктивным поставщиком).

 

 

 

 

 

ai   bj	200	150	150	200	100
250	7	4	3 50	1 100	2 100
200	2	9 100	4 100	2	2
300	1 200	10	12	1 100	9
50	0	0 50	0	0	0

 

 

3. Опорный план должен занимать  клеток. Найденный нами план  занимает 8 клеток. Таким образом, мы нашли первое НБР или первый опорный план.

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

 

ai       bj	200	150	150	200	100
250	7	4	3 50	1 100	2 100	0
200	2	9 100	4 100	2	2	1
300	1 200	10	12	1 100	9	0
50	0	0 50	0	0	0	-8
	1	8	3	1	2

 

5. Выполняется ли второе требование  критерия оптимальности метода  потенциалов? Вычисляем для всех  свободных клеток разности и клетки, для которых эта разность положительна, помечаем знаком плюс, отрицательные разности заносим в соответствующие клетки.

 

ai       bj	200	150	150	200	100
250	7 +	4 -4	3 50	1 100	2 100	0
200	2 +	9 100	4 100	2 +	2 -1	1
300	1 200	10 +	12 +	1 100	9 +	0
50	0 +	0 50	0 +	0 +	0 +	-8
	1	8	3	1	2

 

 

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

 

 

 

 

 

 

 

 

 

 

 

ai       bj	200	150	150	200	100
250	7	4 50	3	1 100	2 100	0
200	2	9 50	4 150	2	2	1
300	1 200	10	12	1 100	9	0
50	0	0 50	0	0	0	-8
	1	8	3	1	2

 

Проверим оптимальности плана:

 

ai       bj	200	150	150	200	100
250	7 +	4 50	3 +	1 100	2 100	0
200	2 -4	9 50	4 150	2 -4	2 -5	5
300	1 200	10 +	12 +	1 100	9 +	0
50	0 +	0 50	0 +	0 +	0 +	-4
	1	4	-1	1	2