Сведение задачи открытого типа к задаче закрытого типа

Выше мы уже отметили, что задача открытого типа решается сведением её к задаче закрытого типа введением фиктивных либо потребителя П_{n +1} с потребностью b_{n +1}= - (при > ), либо поставщика P_{m +1} с запасом a_{m +1}= - (при < ). При этом стоимости c перевозок с фиктивными участниками делается произвольным постоянным числом, например, c =0. Далее задача решается обычным образом. Только ответ формулируется с реальными перевозками (без учёта фиктивных перевозок).

Пример 7. Решить транспортную задачу, предварительно сведя её к задаче закрытого типа:

 

bj ai

 

Решение. Имеем =50+60+90+30=230 и =40+60+50+50=200, то есть ¹ . При этом > , то есть у поставщиков имеется излишки груза. Вводим фиктивного потребителя с b ₅= - =30 единицами груза и нулевыми стоимостями перевозок:

 

bj ai

 

Находим оптимальное решение закрытой задачи:

bj ai

 

Вычисляем стоимость перевозок:

30×3+20×4+10×3+50×3+30×4+30×4+30×3=680.

В ответе не учитываются перевозки к фиктивному потребителю. Таким образом, 30 единиц груза третьего поставщика остаются невостребованными.

Ответ: Матрица перевозок: . Стоимость перевозок F _min=680 у.е.

Упражнения.

1) Составить первоначальный опорный план следующих задач:

а) методом северо-западного угла;

б) методом наименьших затрат:

bj ai						bj ai

Найти решение задачи.

2) Решить транспортные задачи. Первоначальный опорный план составить двумя методами

bj ai						bj ai

 

Приложения

Приложение 1. Задания для индивидуальных работ

Задание ЛП-1

Решить задачу графическим методом (найти оба экстремума целевой функции)

Вариант	Задача	Вариант	Задача
	F =2 x 1+3 x 2®max (min)		F =5 x 1+5 x 2® max (min)
	F =5 x 1-3 x 2® max (min)		F =- x 1- x 2® max (min)
	F =2 x 1+3 x 2® max (min)		F =5 x 1- x 2® max (min)
	F =2 x 1+2 x 2® max (min)		F =4 x 1+2 x 2® max (min)
	F =2 x 1+4 x 2® max (min)		F =-3 x 1- x 2® max (min)

 

 

	F =15 x 1+10 x 2® max (min)		F =2 x 1+3 x 2® max (min)
	F =3 x 1+2 x 2® max (min)		F =4 x 1+6 x 2® max (min)
	F =2 x 1+5 x 2® max (min)		F =- x 1+4 x 2® max (min)
	F =2 x 1- x 2® max (min)		F = x 1+4 x 2® max (min)
	F =3 x 1+2 x 2® max (min)		F = x 1-4 x 2® max (min)

 

	F =2 x 1+4 x 2® max (min)		F =-5 x 1+ x 2® max (min)
	F = x 1-3 x 2® max (min)		F =4 x 1+3 x 2® max (min)
	F =3 x 1- x 2® max (min)		F =2 x 1+3 x 2® max (min)
	F = x 1-2 x 2® max (min)		F =3 x 1- x 2® max (min)
	F =3 x 1+6 x 2® max (min)		F =3 x 1+4 x 2® max (min)

 

Задание ЛП-2

1) Решить задачу линейного программирования (найти оба экстремума):

а) симплекс-методом;

б) методом искусственного базиса.

2) Составить для обеих экстремумов двойственную и найти её решение по решению исходной:

Вариант	Задача	Вариант	Задача
	F = x 1+4 x 2+ x 3®max (min)		F =-2 x 1-2 x 2-2 x 3® max (min)
	F =2 x 1+3 x 2- x 3® max (min)		F =-3 x 1-2 x 2-2 x 3® max (min)
	F = x 1- x 2+ x 3® max (min)		F =-2 x 1+8 x 2+3 x 3® max (min)
	F =5 x 1+2 x 2+ x 3® max (min)		F =6 x 1+7 x 2+9 x 3® max (min)
	F = x 1-8 x 2-3 x 3® max (min)		F =5 x 1+2 x 2+ x 3® max (min)
	F =- x 1-3 x 2- x 3® max (min)		F =6 x 1- x 2+3 x 3® max (min)

 

	F = x 1+4 x 2+3 x 3® max (min)		F =2 x 1+2 x 2- x 3® max (min)
	F =-4 x 1-3 x 2-2 x 3® max (min)		F = x 1+3 x 2+ x 3® max (min)
	F =4 x 1+ x 2+3 x 3® max (min)		F =2 x 1+3 x 2+2 x 3® max (min)
	F = x 1-3 x 2-2 x 3® max (min)		F =2 x 1+2 x 2-5 x 3® max (min)
	F =3 x 1+2 x 2+2 x 3® max (min)		F = x 1+2 x 2+2 x 3® max (min)
	F =3 x 1+2 x 2+3 x 3® max (min)		F =5 x 1+7 x 2+9 x 3® max (min)
	F = x 1+2 x 2+ x 3® max (min)		F = x 1+ x 2-4 x 3® max (min)

 

	F =2 x 1+ x 2+2 x 3® max (min)		F =3 x 1+2 x 2-3 x 3® max (min)
	F =6 x 1+7 x 2+9 x 3® max (min)		F =-3 x 1+ x 2+2 x 3® max (min)

Задание ЛП-3

1) Решить задачу об использовании сырья симплекс-методом. Дать экономическую интерпретацию задачи.

2) Решить задачу о диете (рационе).

Условия задач приведены в таблице. Во всех случаях составить математическую модель задачи.

Значения коэффициентов условия задачи
	Вариант 1			Вариант 2
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 3			Вариант 4
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 5			Вариант 6
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 7			Вариант 8
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj

 

	Вариант 9			Вариант 10
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 11			Вариант 12
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 13			Вариант 14
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 15			Вариант 16
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 17			Вариант 18
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 19			Вариант 20
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 21			Вариант 22
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 23			Вариант 24
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 25			Вариант 26
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 27			Вариант 28
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj
	Вариант 29			Вариант 30
Si	bi	P 1	P 2		Si	bi	P 1	P 2
S 1					S 1
S 2					S 2
S 3					S 3
	cj					cj

 

Задание ЛП-4

 

Решить задачи Задания 1 как задачу целочисленного программирования.

 

Задание ЛП-5

 

Решить задачи Задания 2 как задачу целочисленного программирования.

 

Задание ЛП-6

 

Решить транспортную задачу методом потенциалов. Первоначальный план составить методами северо-западного угла и наименьших затрат.

Значения коэффициентов условия задачи

Вар-т 1

Потребители и их потребности

Вар-т 2

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар-т 3

Потребители и их потребности

Вар-т 4

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар-т 5

Потребители и их потребности

Вар-т 6

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар-т 7

Потребители и их потребности

Вар-т 8

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар-т 9

Потребители и их потребности

Вар. 10

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 11

Потребители и их потребности

Вар. 12

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

 

 

Вар. 13

Потребители и их потребности

Вар. 14

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 15

Потребители и их потребности

Вар. 16

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 17

Потребители и их потребности

Вар. 18

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 19

Потребители и их потребности

Вар. 20

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 21

Потребители и их потребности

Вар. 22

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

Вар. 23

Потребители и их потребности

Вар. 24

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы

 

 

Вар. 25

Потребители и их потребности

Вар. 26

Потребители и их потребности

Пос-тав-щики и их запа- сы

Пос-тав-щики и их запа- сы