Методы оптимальных решений

Размещено на http://www.allbest.ru/

Федеральное государственное бюджетное образовательное учреждение

высшего образования

"Саратовский государственный технический университет

имени Гагарина Ю. А."

Факультет Экономики и менеджмента (ФЭМ)

Кафедра "Математика и моделирование"

Направление 38.03.01 "Экономика"

КОНТРОЛЬНАЯ РАБОТА

Методы оптимальных решений

Вариант № 10

ВЫПОЛНИЛ (А):

Горбунова Вероника Александровна

ПРОВЕРИЛ(А): доктор физико-математических наук,

Профессор Бредихин Дмитрий Александрович

Саратов

2016



Содержание

Задание 1

Задание 2

Задание 3



Задание 1

F = 7x1+x2 > max/min, при системе ограничений:

x1+3x2?2

4x1-2x2?35

5x1-13x2?18

x1 ? 0

x2 ? 0

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

x1+3x2=2 (1) прямая, проходит через точки (2;0) и (-1;1),

4x1-2x2=35 (2) прямая, проходит через точки (9,75; 2) и (8,75; 0)

5x1-13x2=18 (3) прямая, проходит через точки (1; -1) и (3,6; 0)

x1 = 0 (4) ось Ох2

x2 = 0 (5) ось Ох1

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

Обозначим границы области многоугольника решений.

Построим прямую, отвечающую значению функции F = 0: F = 7x1+x2 = 0.

Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (7; 1)

Определим границы ограниченной области:

1) Так как точка A получена в результате пересечения прямых (5) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

2) Так как точка B получена в результате пересечения прямых (2) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

3) Так как точка С получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Сравним значения целевой функции в вершинах области:

F(A)= 7*3,6 + 1*0 = 25,2 минимальное значение

F(B)= 7*8,75 + 1*0 = 61,25

F(C) = 7*9,98+1*2,45 = 72,29 максимальное значение

Ответ: максимальное значение целевой функции F(X) = 72,29 в точке ; минимальное значение целевой функции F(X) = 25,2 в точке .

Задание 2

Так как нужно определить объёмы производства каждого вида продукции, переменными являются:

X1 - объём производства изделия А в шт.

Х2 - объём производства изделия В в шт.

Целевая функция. Так как стоимость 1 изделия А равна16 руб., доход от её продажи составит 16Х1 руб. Аналогично доход от реализации изделия В составит 19Х2 руб. При допущении независимости объёмов сбыта каждого из изделий общий доход равен сумме двух слагаемых - дохода от продажи изделий А и дохода от продажи изделий В.

Обозначив доход (в руб.) через f(X), можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения X1 и Х2, максимизирующие величину общего дохода:

f(X) = 16X1 + 19X2

Составим математическую модель задачи:

Исходный продукт	Расход исходных продуктов на 1 изделие (кг)	Максимально возможный запас (кг)
	А	В
I	а1	в1	с1
II	а2	в2	с2
III	а3	в3	с3
Прибыль	б	в

Максимальное значение целевой функции F(X) = 16x1+19x2 при следующих условиях-ограничений.

19x1+31x2?1121

16x1+9x2?706

19x1+x2?1068

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

19x1 + 31x2 + 1x3 + 0x4 + 0x5 = 1121

16x1 + 9x2 + 0x3 + 1x4 + 0x5 = 706

19x1 + 1x2 + 0x3 + 0x4 + 1x5 = 1068

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

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

Решим систему уравнений относительно базисных переменных: x3, x4, x5

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,1121,706,1068)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5
x3	1121	19	31	1	0	0
x4	706	16	9	0	1	0
x5	1068	19	1	0	0	1
F(X0)	0	-16	-19	0	0	0

Переходим к основному алгоритму симплекс-метода.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:

min (1121 : 31 , 706 : 9 , 1068 : 1 ) = 365/31

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3	1121	19	31	1	0	0	365/31
x4	706	16	9	0	1	0	784/9
x5	1068	19	1	0	0	1	1068
F(X1)	0	-16	-19	0	0	0	0

Вместо переменной x3 в план 1 войдет переменная x2.

Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x3 плана 0 на разрешающий элемент =31. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
1121 : 31	19 : 31	31 : 31	1 : 31	0 : 31	0 : 31
706-(1121 * 9):31	16-(19 * 9):31	9-(31 * 9):31	0-(1 * 9):31	1-(0 * 9):31	0-(0 * 9):31
1068-(1121 * 1):31	19-(19 * 1):31	1-(31 * 1):31	0-(1 * 1):31	0-(0 * 1):31	1-(0 * 1):31
0-(1121 * -19):31	-16-(19 * -19):31	-19-(31 * -19):31	0-(1 * -19):31	0-(0 * -19):31	0-(0 * -19):31

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	365/31	19/31	1	1/31	0	0
x4	38017/31	1015/31	0	-9/31	1	0
x5	103126/31	1812/31	0	-1/31	0	1
F(X1)	6872/31	-411/31	0	19/31	0	0

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (365/31 : 19/31 , 38017/31 : 1015/31 , 103126/31 : 1812/31 ) = 3697/325 полуплоскость неравенство целевой многоугольник

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (1015/31) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x2	365/31	19/31	1	1/31	0	0	59
x4	38017/31	1015/31	0	-9/31	1	0	3697/325
x5	103126/31	1812/31	0	-1/31	0	1	5667/570
F(X2)	6872/31	-411/31	0	19/31	0	0	0

Вместо переменной x4 в план 2 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент =1015/31. На месте разрешающего элемента получаем 1. В остальных клетках столбца x1 записываем нули.

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

Представим расчет каждого элемента в виде таблицы:

B	x1	x2	x3	x4	x5
365/31-(38017/31 * 19/31):1015/31	19/31-(1015/31 * 19/31):1015/31	1-(0 * 19/31):1015/31	1/31-(-9/31 * 19/31):1015/31	0-(1 * 19/31):1015/31	0-(0 * 19/31):1015/31
38017/31 : 1015/31	1015/31 : 1015/31	0 : 1015/31	-9/31 : 1015/31	1 : 1015/31	0 : 1015/31
103126/31-(38017/31 * 1812/31):1015/31	1812/31-(1015/31 * 1812/31):1015/31	0-(0 * 1812/31):1015/31	-1/31-(-9/31 * 1812/31):1015/31	0-(1 * 1812/31):1015/31	1-(0 * 1812/31):1015/31
6872/31-(38017/31 * -411/31):1015/31	-411/31-(1015/31 * -411/31):1015/31	0-(0 * -411/31):1015/31	19/31-(-9/31 * -411/31):1015/31	0-(1 * -411/31):1015/31	0-(0 * -411/31):1015/31

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x2	13297/325	0	1	16/325	-19/325	0
x1	3697/325	1	0	-9/325	31/325	0
x5	36427/65	0	0	31/65	-149/65	1
F(X2)	8459/65	0	0	32/65	27/65	0

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:



Базис	B	x1	x2	x3	x4	x5
x2	13297/325	0	1	16/325	-19/325	0
x1	3697/325	1	0	-9/325	31/325	0
x5	36427/65	0	0	31/65	-149/65	1
F(X3)	8459/65	0	0	32/65	27/65	0

Оптимальный план можно записать так:

x1 = 3697/325?36,3, x2 = 13297/325? 13,9

F(X) = 16*3697/325 + 19*13297/325 = 8459/65? 845,14

Ответ: Максимальная прибыль составит 8459/65? 845,14 руб при реализации 3697/325?36,3, изделий вида А и 13297/325? 13,9изделий вида В.

Задание 3

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

	1	2	3	4	5	Запасы
1	20	10	13	13	18	200
2	27	19	20	16	22	300
3	26	17	19	21	23	250
Потребности	210	150	120	135	135

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

?a = 200 + 300 + 250 = 750

?b = 210 + 150 + 120 + 135 + 135 = 750

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

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

План начинается заполняться с верхнего левого угла. Искомый элемент равен 20. Для этого элемента запасы равны 200, потребности 210. Поскольку минимальным является 200, то вычитаем его. x11 = min(200,210) = 200.

Движемся вправо по строке - искомый элемент равен 27. Для этого элемента запасы равны 300, потребности 10. Поскольку минимальным является 10, то вычитаем его. x21 = min(300,10) = 10..

Далее искомый элемент равен 19. Для этого элемента запасы равны 290, потребности 150. Поскольку минимальным является 150, то вычитаем его. x22 = min(290,150) = 150.

Искомый элемент равен 20. Для этого элемента запасы равны 140, потребности 120. Поскольку минимальным является 120, то вычитаем его. x23 = min(140,120) = 120.

Искомый элемент равен 16. Для этого элемента запасы равны 20, потребности 135. Поскольку минимальным является 20, то вычитаем его. x24 = min(20,135) = 20.

Искомый элемент равен 16. Для этого элемента запасы равны 20, потребности 135. Поскольку минимальным является 20, то вычитаем его. x24 = min(20,135) = 20.

Искомый элемент равен 23. Для этого элемента запасы равны 135, потребности 135. Поскольку минимальным является 135, то вычитаем его. x35 = min(135,135) = 135.

Получили следующий опорный план:

Таблица 1

	1	2	3	4	5	Запасы
1	20[200]	10	13	13	18	200
2	27[10]	19[150]	20[120]	16[20]	22	300
3	26	17	19	21[115]	23[135]	250
Потребности	210	150	120	135	135



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

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

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

F(x) = 20*200 + 27*10 + 19*150 + 20*120 + 16*20 + 21*115 + 23*135 = 15360

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20

u2 + v1 = 27; 20 + u2 = 27; u2 = 7

u2 + v2 = 19; 7 + v2 = 19; v2 = 12

u2 + v3 = 20; 7 + v3 = 20; v3 = 13

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

u3 + v4 = 21; 9 + u3 = 21; u3 = 12

u3 + v5 = 23; 12 + v5 = 23; v5 = 11

Таблица 2

	v1=20	v2=12	v3=13	v4=9	v5=11
u1=0	20[200]	10	13	13	18
u2=7	27[10]	19[150]	20[120]	16[20]	22
u3=12	26	17	19	21[115]	23[135]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 12 > 10; ?12 = 0 + 12 - 10 = 2

(3;1): 12 + 20 > 26; ?31 = 12 + 20 - 26 = 6

(3;2): 12 + 12 > 17; ?32 = 12 + 12 - 17 = 7

(3;3): 12 + 13 > 19; ?33 = 12 + 13 - 19 = 6

max(2,6,7,6) = 7

Выбираем максимальную оценку свободной клетки (3;2): 17

Для этого в перспективную клетку (3;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Таблица 3

Цикл приведен в таблице (3,2 > 3,4 > 2,4 > 2,2).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 4) = 115. Прибавляем 115 к объемам грузов, стоящих в плюсовых клетках и вычитаем 115 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 4

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; -v1 = 20

u2 + v1 = 27; 20 + u2 = 27; u2 = 7

u2 + v2 = 19; 7 + v2 = 19; v2 = 12

u3 + v2 = 17; 12 + u3 = 17; u3 = 5

u3 + v5 = 23; 5 + v5 = 23; v5 = 18

u2 + v3 = 20; 7 + v3 = 20; v3 = 13

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

Таблица 5

	v1=20	v2=12	v3=13	v4=9	v5=18
u1=0	20[200]	10	13	13	18
u2=7	27[10]	19[35]	20[120]	16[135]	22
u3=5	26	17[115]	19	21	23[135]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 12 > 10; ?12 = 0 + 12 - 10 = 2

(2;5): 7 + 18 > 22; ?25 = 7 + 18 - 22 = 3

max(2,3) = 3

Выбираем максимальную оценку свободной клетки (2;5): 22

Для этого в перспективную клетку (2;5) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Таблица 6

Цикл приведен в таблице (2,5 > 2,2 > 3,2 > 3,5).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 35. Прибавляем 35 к объемам грузов, стоящих в плюсовых клетках и вычитаем 35 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 7

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v1 = 20; 0 + v1 = 20; v1 = 20

u2 + v1 = 27; 20 + u2 = 27; u2 = 7

u2 + v3 = 20; 7 + v3 = 20; v3 = 13

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

u2 + v5 = 22; 7 + v5 = 22; v5 = 15

u3 + v5 = 23; 15 + u3 = 23; u3 = 8

u3 + v2 = 17; 8 + v2 = 17; v2 = 9

Таблица 8

	v1=20	v2=9	v3=13	v4=9	v5=15
u1=0	20[200]	10	13	13	18
u2=7	27[10]	19	20[120]	16[135]	22[35]
u3=8	26	17[150]	19	21	23[100]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(3;1): 8 + 20 > 26; ?31 = 8 + 20 - 26 = 2

(3;3): 8 + 13 > 19; ?33 = 8 + 13 - 19 = 2

max(2,2) = 2

Выбираем максимальную оценку свободной клетки (3;1): 26

Для этого в перспективную клетку (3;1) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Таблица 9

Цикл приведен в таблице (3,1 > 3,5 > 2,5 > 2,1).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 10

u1 + v1 = 20; 0 + v1 = 20; v1 = 20

u3 + v1 = 26; 20 + u3 = 26; u3 = 6

u3 + v2 = 17; 6 + v2 = 17; v2 = 11

u3 + v5 = 23; 6 + v5 = 23; v5 = 17

u2 + v5 = 22; 17 + u2 = 22; u2 = 5

u2 + v3 = 20; 5 + v3 = 20; v3 = 15

u2 + v4 = 16; 5 + v4 = 16; v4 = 11

Таблица 11

	v1=20	v2=11	v3=15	v4=11	v5=17
u1=0	20[200]	10	13	13	18
u2=5	27	19	20[120]	16[135]	22[45]
u3=6	26[10]	17[150]	19	21	23[90]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 11 > 10; ?12 = 0 + 11 - 10 = 1

(1;3): 0 + 15 > 13; ?13 = 0 + 15 - 13 = 2

(3;3): 6 + 15 > 19; ?33 = 6 + 15 - 19 = 2

max(1,2,2) = 2

Выбираем максимальную оценку свободной клетки (1;3): 13

Для этого в перспективную клетку (1;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Таблица 12

Цикл приведен в таблице (1,3 > 1,1 > 3,1 > 3,5 > 2,5 > 2,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 13

u1 + v1 = 20; 0 + v1 = 20; v1 = 20

u3 + v1 = 26; 20 + u3 = 26; u3 = 6

u3 + v2 = 17; 6 + v2 = 17; v2 = 11

u1 + v3 = 13; 0 + v3 = 13; v3 = 13

u2 + v3 = 20; 13 + u2 = 20; u2 = 7

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

u2 + v5 = 22; 7 + v5 = 22; v5 = 15

Таблица 14

	v1=20	v2=11	v3=13	v4=9	v5=15
u1=0	20[110]	10	13[90]	13	18
u2=7	27	19	20[30]	16[135]	22[135]
u3=6	26[100]	17[150]	19	21	23

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(1;2): 0 + 11 > 10; ?12 = 0 + 11 - 10 = 1

Выбираем максимальную оценку свободной клетки (1;2): 10

Для этого в перспективную клетку (1;2) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".



Таблица 15

Цикл приведен в таблице (1,2 > 1,1 > 3,1 > 3,2).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 110. Прибавляем 110 к объемам грузов, стоящих в плюсовых клетках и вычитаем 110 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

Таблица 16

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 10; 0 + v2 = 10; v2 = 10

u3 + v2 = 17; 10 + u3 = 17; u3 = 7

u3 + v1 = 26; 7 + v1 = 26; v1 = 19

u1 + v3 = 13; 0 + v3 = 13; v3 = 13

u2 + v3 = 20; 13 + u2 = 20; u2 = 7

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

u2 + v5 = 22; 7 + v5 = 22; v5 = 15

Таблица 17

	v1=19	v2=10	v3=13	v4=9	v5=15
u1=0	20	10[110]	13[90]	13	18
u2=7	27	19	20[30]	16[135]	22[135]
u3=7	26[210]	17[40]	19	21	23

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij

(3;3): 7 + 13 > 19; ?33 = 7 + 13 - 19 = 1

Выбираем максимальную оценку свободной клетки (3;3): 19

Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-".

Таблица 18

Цикл приведен в таблице (3,3 > 3,2 > 1,2 > 1,3).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.



Таблица 19

Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.

u1 + v2 = 10; 0 + v2 = 10; v2 = 10

u1 + v3 = 13; 0 + v3 = 13; v3 = 13

u2 + v3 = 20; 13 + u2 = 20; u2 = 7

u2 + v4 = 16; 7 + v4 = 16; v4 = 9

u2 + v5 = 22; 7 + v5 = 22; v5 = 15

u3 + v3 = 19; 13 + u3 = 19; u3 = 6

u3 + v1 = 26; 6 + v1 = 26; v1 = 20

Таблица 20

	v1=20	v2=10	v3=13	v4=9	v5=15
u1=0	20	10[150]	13[50]	13	18
u2=7	27	19	20[30]	16[135]	22[135]
u3=6	26[210]	17	19[40]	21	23

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ? cij.

Минимальные затраты составят: F(x) = 10*150 + 13*50 + 20*30 + 16*135 + 22*135 + 26*210 + 19*40 = 14100

Ответ: Минимальные затраты составят: F(x) = 14100

При этом из 1-го склада необходимо направить во 2-й магазин 150 единиц груза, в 3-й магазин 50 единиц груза. Из 2-го склада необходимо направить в 3-й магазин 30 единиц груза, в 4-й магазин 135 единиц груза, в 5-й магазин 135 единиц груза. Из 3-го склада необходимо направить в 1-й магазин 210 единиц груза, в 3-й магазин 40 единиц груза.

Размещено на Allbest.ru

...