Симплексный метод

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

Московский Государственный Строительный Университет

Факультет: Экономика и Производственный Менеджмент

Контрольная работа

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

Егорьевск 2014г



Задание №1. Решить задачи симплексным методом.

В-4. Z(X) = x1 + 2x2 + 2x3 ® min,

Решение:

Симплекс-метод.

Решим прямую задачу линейного программирования симплекс-методом.

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

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

При вычислениях значение Fc = -4 временно не учитываем.

x1 + x2 - 4x3?1

x1 - 2x2 + 2x3=2

x1 + 2x2 - 2x3?6

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

В 1-м неравенстве смысла (?) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (?) вводим базисную переменную x5.

1x1 + 1x2-4x3-1x4 + 0x5 = 1

1x1-2x2 + 2x3 + 0x4 + 0x5 = 2

1x1 + 2x2-2x3 + 0x4 + 1x5 = 6



Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7;

1x1 + 1x2-4x3-1x4 + 0x5 + 1x6 + 0x7 = 1

1x1-2x2 + 2x3 + 0x4 + 0x5 + 0x6 + 1x7 = 2

1x1 + 2x2-2x3 + 0x4 + 1x5 + 0x6 + 0x7 = 6

Для постановки задачи на минимум целевую функцию запишем так:

F(X) = Mx4+Mx5+Mx6+Mx7 > min

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

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

Из уравнений выражаем искусственные переменные:

x6 = 1-x1-x2+4x3+x4

x7 = 2-x1+2x2-2x3

которые подставим в целевую функцию:

F(X) = M(1-x1-x2+4x3+x4) + M(2-x1+2x2-2x3) > min

или

F(X) = (-2M)x1+(M)x2+(2M)x3+(M)x4+(3M) > min

Введем новую переменную x0 = - 2x1 + x2 + 2x3.

Выразим базисные переменные <6, 7, 5> через небазисные.

x0 = 3-2x1+x2+2x3+x4

x6 = 1-x1-x2+4x3+x4

x7 = 2-x1+2x2-2x3

x5 = 6-x1-2x2+2x3

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

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

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(-2,1,2,1,0,0,0) = -2

x0 = 3-2x1+x2+2x3+x4

x6 = 1-x1-x2+4x3+x4

x7 = 2-x1+2x2-2x3

x5 = 6-x1-2x2+2x3

В качестве новой переменной выбираем x1.

3. Определение новой свободной переменной.

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

min (1 : 1 , 2 : 1 , 6 : 1 ) = 1

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

4. Пересчет всех уравнений.

Выразим переменную x1 через x6

x1 = 1-x2+4x3+x4-x6

и подставим во все выражения.

x0 = 3-2(1-x2+4x3+x4-x6)+x2+2x3+x4

x7 = 2-(1-x2+4x3+x4-x6)+2x2-2x3

x5 = 6-(1-x2+4x3+x4-x6)-2x2+2x3

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 1+3x2-6x3-x4+2x6

x1 = 1-x2+4x3+x4-x6

x7 = 1+3x2-6x3-x4+x6

x5 = 5-x2-2x3-x4+x6

Полагая небазисные переменные x = (1, 7, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, -3, 6, 1, 0, -2, 0), x0 = 1

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(0,3,-6,-1,0,2,0) = -6

x0 = 1+3x2-6x3-x4+2x6

x1 = 1-x2+4x3+x4-x6

x7 = 1+3x2-6x3-x4+x6

x5 = 5-x2-2x3-x4+x6

В качестве новой переменной выбираем x3.

3. Определение новой свободной переменной.

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

min (- , 1 : 6 , 5 : 2 ) = 1/6

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

4. Пересчет всех уравнений.

Выразим переменную x3 через x7

x3 = 1/6+1/2x2-1/6x4+1/6x6-1/6x7

и подставим во все выражения.

x0 = 1+3x2-6(1/6+1/2x2-1/6x4+1/6x6-1/6x7)-x4+2x6

x1 = 1-x2+4(1/6+1/2x2-1/6x4+1/6x6-1/6x7)+x4-x6

x5 = 5-x2-2(1/6+1/2x2-1/6x4+1/6x6-1/6x7)-x4+x6

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = 0+x6+x7

x1 = 5/3+x2+1/3x4-1/3x6-2/3x7

x3 = 1/6+1/2x2-1/6x4+1/6x6-1/6x7

x5 = 14/3-2x2-2/3x4+2/3x6+1/3x7

Полагая небазисные переменные x = (1, 3, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, 0, 0, -1, -1), x0 = 0

Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.

x0 = 0+x6+x7

x1 = 5/3+x2+1/3x4-1/3x6-2/3x7

x3 = 1/6+1/2x2-1/6x4+1/6x6-1/6x7

x5 = 14/3-2x2-2/3x4+2/3x6+1/3x7

На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.

x1 = 5/3+x2+1/3x4

x3 = 1/6+1/2x2-1/6x4

x5 = 14/3-2x2-2/3x4

Выразим базисные переменные:

x1 = 5/3+x2+1/3x4

x3 = 1/6+1/2x2-1/6x4

которые подставим в целевую функцию:

F(X) = (5/3+x2+1/3x4) + 2x2 + 2(1/6+1/2x2-1/6x4)-4x4

или

F(X) = 2+4x2-4x4

Получаем новую систему переменных.

x0 = 2+4x2-4x4

x1 = 5/3+x2+1/3x4

x3 = 1/6+1/2x2-1/6x4

x5 = 14/3-2x2-2/3x4

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(0,4,0,-4,0) = -4

x0 = 2+4x2-4x4

x1 = 5/3+x2+1/3x4

x3 = 1/6+1/2x2-1/6x4

x5 = 14/3-2x2-2/3x4

В качестве новой переменной выбираем x4.

3. Определение новой свободной переменной.

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

min (- , 1/6 : 1/6 , 42/3 : 2/3 ) = 1

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

4. Пересчет всех уравнений.

Выразим переменную x4 через x3

x4 = 1+3x2-6x3

и подставим во все выражения.

x0 = 2+4x2-4(1+3x2-6x3)

x1 = 12/3+x2+1/3(1+3x2-6x3)

x5 = 42/3-2x2-2/3(1+3x2-6x3)

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = -2-8x2+24x3

x1 = 2+2x2-2x3

x4 = 1+3x2-6x3

x5 = 4-4x2+4x3

Полагая небазисные переменные x = (1, 4, 5) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 8, -24, 0, 0), x0 = -2

1. Проверка критерия оптимальности.

В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален

2. Определение новой базисной переменной.

max(0,-8,24,0,0) = -8

x0 = -2-8x2+24x3

x1 = 2+2x2-2x3

x4 = 1+3x2-6x3

x5 = 4-4x2+4x3

В качестве новой переменной выбираем x2.

3. Определение новой свободной переменной.

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

min (- , - , 4 : 4 ) = 1

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

4. Пересчет всех уравнений.

Выразим переменную x2 через x5

x2 = 1+x3-1/4x5

и подставим во все выражения.

x0 = -2-8(1+x3-1/4x5)+24x3

x1 = 2+2(1+x3-1/4x5)-2x3

x4 = 1+3(1+x3-1/4x5)-6x3

После приведения всех подобных, получаем новую систему, эквивалентную прежней:

x0 = -10+16x3+2x5

x1 = 4-1/2x5

x4 = 4-3x3-3/4x5

x2 = 1+x3-1/4x5

Полагая небазисные переменные x = (1, 4, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, -16, 0, -2), x0 = -10

Выражение для x0 не содержит отрицательных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

x0 = -10+16x3+2x5

x1 = 4-1/2x5

x4 = 4-3x3-3/4x5

x2 = 1+x3-1/4x5

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.

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

x1 = 4

x2 = 1

F(X) = 1*4 + 2*1 -4 = 2

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

	О1	О2	О3	О4	О5	наличие
Б1	2	10	15	14	4	150
Б2	3	7	12	5	8	170
Б3	21	18	6	13	16	260
потребность	100	90	160	150	80

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

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

F = ??cijxij, (1)

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

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

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

xij ? 0

Запишем экономико-математическую модель для нашей задачи.

Переменные:

x11 - количество груза из 1-го склада в 1-й магазин

x12 - количество груза из 1-го склада в 2-й магазин

x13 - количество груза из 1-го склада в 3-й магазин

x14 - количество груза из 1-го склада в 4-й магазин

x15 - количество груза из 1-го склада в 5-й магазин

x21 - количество груза из 2-го склада в 1-й магазин

x22 - количество груза из 2-го склада в 2-й магазин

x23 - количество груза из 2-го склада в 3-й магазин

x24 - количество груза из 2-го склада в 4-й магазин

x25 - количество груза из 2-го склада в 5-й магазин

x31 - количество груза из 3-го склада в 1-й магазин

x32 - количество груза из 3-го склада в 2-й магазин

x33 - количество груза из 3-го склада в 3-й магазин

x34 - количество груза из 3-го склада в 4-й магазин

x35 - количество груза из 3-го склада в 5-й магазин

Ограничения по запасам:

x11 + x12 + x13 + x14 + x15 ? 150

x21 + x22 + x23 + x24 + x25 ? 170

x31 + x32 + x33 + x34 + x35 ? 260

Ограничения по потребностям:

x11 + x21 + x31 ? 100

x12 + x22 + x32 ? 90

x13 + x23 + x33 ? 160

x14 + x24 + x34 ? 150

x15 + x25 + x35 ? 80

Целевая функция:

2x11 + 10x12 + 15x13 + 14x14 + 4x15 + 3x21 + 7x22 + 12x23 + 5x24 + 8x25 + 21x31 + 18x32 + 6x33 + 13x34 + 16x35 > min

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

	О1	О2	О3	О4	О5	Наличие
Б1	2	10	15	14	4	150
Б2	3	7	12	5	8	170
Б3	21	18	6	13	16	260
Потребности	100	90	160	150	80

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

?a = 150 + 170 + 260 = 580

?b = 100 + 90 + 160 + 150 + 80 = 580

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

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

линейный программирование потенциал переменная

	О1	О2	О3	О4	О5	Наличие
Б1	2	10	15	14	4	150
Б2	3	7	12	5	8	170
Б3	21	18	6	13	16	260
Потребности	100	90	160	150	80

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

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

План начинается заполняться с верхнего левого угла.

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

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

x11 = min(150,100) = 100.

2	10	15	14	4	150 - 100 = 50
x	7	12	5	8	170
x	18	6	13	16	260
100 - 100 = 0	90	160	150	80	0

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

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

x12 = min(50,90) = 50.

2	10	x	x	x	50 - 50 = 0
x	7	12	5	8	170
x	18	6	13	16	260
0	90 - 50 = 40	160	150	80	0

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

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

x22 = min(170,40) = 40.

2	10	x	x	x	0
x	7	12	5	8	170 - 40 = 130
x	x	6	13	16	260
0	40 - 40 = 0	160	150	80	0

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

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

x23 = min(130,160) = 130.

2	10	x	x	x	0
x	7	12	x	x	130 - 130 = 0
x	x	6	13	16	260
0	0	160 - 130 = 30	150	80	0

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

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

x33 = min(260,30) = 30.

2	10	x	x	x	0
x	7	12	x	x	0
x	x	6	13	16	260 - 30 = 230
0	0	30 - 30 = 0	150	80	0

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

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

x34 = min(230,150) = 150.

2	10	x	x	x	0
x	7	12	x	x	0
x	x	6	13	16	230 - 150 = 80
0	0	0	150 - 150 = 0	80	0

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

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

x35 = min(80,80) = 80.

2	10	x	x	x	0
x	7	12	x	x	0
x	x	6	13	16	80 - 80 = 0
0	0	0	0	80 - 80 = 0	0
	1	2	3	4	5	Наличие
1	2[100]	10[50]	15	14	4	150
2	3	7[40]	12[130]	5	8	170
3	21	18	6[30]	13[150]	16[80]	260
Потребности	100	90	160	150	80

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

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

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

F(x) = 2*100 + 10*50 + 7*40 + 12*130 + 6*30 + 13*150 + 16*80 = 5950

Этап II. Улучшение опорного плана.

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

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

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

u2 + v2 = 7; 10 + u2 = 7; u2 = -3

u2 + v3 = 12; -3 + v3 = 12; v3 = 15

u3 + v3 = 6; 15 + u3 = 6; u3 = -9

u3 + v4 = 13; -9 + v4 = 13; v4 = 22

u3 + v5 = 16; -9 + v5 = 16; v5 = 25

	v1=2	v2=10	v3=15	v4=22	v5=25
u1=0	2[100]	10[50]	15	14	4
u2=-3	3	7[40]	12[130]	5	8
u3=-9	21	18	6[30]	13[150]	16[80]

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

(1;4): 0 + 22 > 14; ?14 = 0 + 22 - 14 = 8

(1;5): 0 + 25 > 4; ?15 = 0 + 25 - 4 = 21

(2;4): -3 + 22 > 5; ?24 = -3 + 22 - 5 = 14

(2;5): -3 + 25 > 8; ?25 = -3 + 25 - 8 = 14

max(8,21,14,14) = 21

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

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

	1	2	3	4	5	Наличие
1	2[100]	10[50][-]	15	14	4[+]	150
2	3	7[40][+]	12[130][-]	5	8	170
3	21	18	6[30][+]	13[150]	16[80][-]	260
Потребности	100	90	160	150	80

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

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

	1	2	3	4	5	Наличие
1	2[100]	10	15	14	4[50]	150
2	3	7[90]	12[80]	5	8	170
3	21	18	6[80]	13[150]	16[30]	260
Потребности	100	90	160	150	80

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

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u1 + v5 = 4; 0 + v5 = 4; v5 = 4

u3 + v5 = 16; 4 + u3 = 16; u3 = 12

u3 + v3 = 6; 12 + v3 = 6; v3 = -6

u2 + v3 = 12; -6 + u2 = 12; u2 = 18

u2 + v2 = 7; 18 + v2 = 7; v2 = -11

u3 + v4 = 13; 12 + v4 = 13; v4 = 1

	v1=2	v2=-11	v3=-6	v4=1	v5=4
u1=0	2[100]	10	15	14	4[50]
u2=18	3	7[90]	12[80]	5	8
u3=12	21	18	6[80]	13[150]	16[30]

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

(2;1): 18 + 2 > 3; ?21 = 18 + 2 - 3 = 17

(2;4): 18 + 1 > 5; ?24 = 18 + 1 - 5 = 14

(2;5): 18 + 4 > 8; ?25 = 18 + 4 - 8 = 14

max(17,14,14) = 17

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

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

	1	2	3	4	5	Наличие
1	2[100][-]	10	15	14	4[50][+]	150
2	3[+]	7[90]	12[80][-]	5	8	170
3	21	18	6[80][+]	13[150]	16[30][-]	260
Потребности	100	90	160	150	80

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

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



	1	2	3	4	5	Наличие
1	2[70]	10	15	14	4[80]	150
2	3[30]	7[90]	12[50]	5	8	170
3	21	18	6[110]	13[150]	16	260
Потребности	100	90	160	150	80

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

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 3; 2 + u2 = 3; u2 = 1

u2 + v2 = 7; 1 + v2 = 7; v2 = 6

u2 + v3 = 12; 1 + v3 = 12; v3 = 11

u3 + v3 = 6; 11 + u3 = 6; u3 = -5

u3 + v4 = 13; -5 + v4 = 13; v4 = 18

u1 + v5 = 4; 0 + v5 = 4; v5 = 4

	v1=2	v2=6	v3=11	v4=18	v5=4
u1=0	2[70]	10	15	14	4[80]
u2=1	3[30]	7[90]	12[50]	5	8
u3=-5	21	18	6[110]	13[150]	16

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

(1;4): 0 + 18 > 14; ?14 = 0 + 18 - 14 = 4

(2;4): 1 + 18 > 5; ?24 = 1 + 18 - 5 = 14, max(4,14) = 14

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

Для этого в перспективную клетку (2;4) поставим знак «+»

	1	2	3	4	5	Наличие
1	2[70]	10	15	14	4[80]	150
2	3[30]	7[90]	12[50][-]	5[+]	8	170
3	21	18	6[110][+]	13[150][-]	16	260
Потребности	100	90	160	150	80

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

	1	2	3	4	5	Наличие
1	2[70]	10	15	14	4[80]	150
2	3[30]	7[90]	12	5[50]	8	170
3	21	18	6[160]	13[100]	16	260
Потребности	100	90	160	150	80

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

u1 + v1 = 2; 0 + v1 = 2; v1 = 2

u2 + v1 = 3; 2 + u2 = 3; u2 = 1

u2 + v2 = 7; 1 + v2 = 7; v2 = 6

u2 + v4 = 5; 1 + v4 = 5; v4 = 4

u3 + v4 = 13; 4 + u3 = 13; u3 = 9

u3 + v3 = 6; 9 + v3 = 6; v3 = -3

u1 + v5 = 4; 0 + v5 = 4; v5 = 4

	v1=2	v2=6	v3=-3	v4=4	v5=4
u1=0	2[70]	10	15	14	4[80]
u2=1	3[30]	7[90]	12	5[50]	8
u3=9	21	18	6[160]	13[100]	16

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

Минимальные затраты составят:

F(x) = 2*70 + 4*80 + 3*30 + 7*90 + 5*50 + 6*160 + 13*100 = 3690

Анализ оптимального плана.

Из 1-го склада необходимо груз направить в 1-й магазин (70), в 5-й магазин (80).

Из 2-го склада необходимо груз направить в 1-й магазин (30), в 2-й магазин (90), в 4-й магазин (50).

Из 3-го склада необходимо груз направить в 3-й магазин (160), в 4-й магазин (100).

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