Градиент 11782

Из таблицы 2-го шага имеем F*₂(e¹ = 4) = 46. То есть максимальный доход всей системы при количестве средств e¹ = 4 равен 46

Из этой же таблицы получаем, что 2-му предприятию следует выделить u*₂(e¹ =4) = 0

При этом остаток средств составит:

e² = e¹ - u²

e² = 4 - 4 = 0

Последнему предприятию достается 0

Итак, инвестиции в размере 6 необходимо распределить следующим образом:

1-му предприятию выделить 2

2-му предприятию выделить 4

3-му предприятию выделить 0

Что обеспечит максимальный доход, равный70

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

Если выделить 6 усл. Ден. ед. предприятию П₁, то получим прибыль 63.

((70-63)/70)*100%=10%

Если выделить 6 усл. Ден. ед. предприятию П₁, то получим прибыль 61.

((70-61)/70)*100%=12,86%

Если выделить 6 усл. Ден. ед. предприятию П₁, то получим прибыль 69.

((70-69)/70)*100%=1,43%

Если распределить инвестиции поровну между всеми предприятиями, т.е. каждому предприятию выделить по 2 усл. Ден. ед, то прибыль будет равна 24+27+18=69.

((70-69)/70)*100%=1,43%

Задача 2

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

M	Т1		Т2		Т3
	m	r	m	r	m	r
83	12	22	17	31	27	48

Решение:

Максимальное место в транспортном средстве составляет 83 ед. Место, которое занимает 1 единица груза Т₁ составляет 12 ед. Тогда максимальное число груза Т₁, которое можно поместить в транспортное средство равно [83/12]=6. Место, которое занимает 1 единица груза Т₂ составляет 17 ед. Тогда максимальное число груза Т₂, которое можно поместить в транспортное средство равно [83/17]=4. Место, которое занимает 1 единица груза Т₃ составляет 27 ед. Тогда максимальное число груза Т₃, которое можно поместить в транспортное средство равно [83/27]=3.

Стоимость 1 единицы груза Т₁ равна 22, груза Т₂ равна 31, груза Т₃ равна 48.

Предмет Т₁ можно погрузить в количестве 0,1,2,3,4,5,6. Предмет Т₂ можно погрузить в количестве 0,1,2,3,4. Предмет Т₃ можно погрузить в количестве 0,1,2,3.

Составим таблицу распределения предметов в транспортном средстве и стоимости перевозимого груза.

Т1	Т2	Т3	Стоимость для груза Т1	Стоимость для груза Т2	Стоимость для груза Т3	Общая стоимость груза
6	0	0	132	0	0	132
5	1	0	110	31	0	141
4	2	0	88	62	0	150
4	0	1	88	0	48	136
3	2	0	66	62	0	128
3	1	1	66	31	48	145
2	3	0	44	93	0	137
2	1	1	44	31	48	123
2	0	2	44	0	96	140
1	4	0	22	124	0	146
1	2	1	22	62	48	132
1	1	2	22	31	96	149
0	4	0	0	124	0	124
0	3	1	0	93	48	141
0	1	2	0	31	96	127
0	0	3	0	0	144	144

Из таблицы видно, что максимальная стоимость груза будет, если перевозить 4 единицы груза Т₁, 2 единицы груза Т₂ и 0 единиц груза Т₃. Стоимость груза в данном случае будет равна 150 усл. Ед.

Если перевозить 6 единиц груза Т₁, то стоимость груза равна 132. Тогда теряется ((150-145)/150)*100%=3,33 % стоимости груза.

Если перевозить 4 единиц груза Т₁, то стоимость груза равна 124. Тогда теряется ((150-12/150)*100%=17,33% стоимости груза.

Если перевозить 3 единиц груза Т₁, то стоимость груза равна 144. Тогда теряется ((150-144)/150)*100%= 4% стоимости груза.

Задача 3

Имеются четыре овощехранилища, расположенные в разных районах города, в которых сосредоточено 10, 20, 35 и 45 т овощей соответственно. Овощи необходимо перевезти четырем потребителям соответственно в количестве25, 30, 40 и 15т. Расстояния от овощехранилища до потребителей следующие.

Хранилище	Потребители
	П1	П2	П3	П4
1	7	3	3	8
2	7	6	2	7
3	4	7	7	3
4	5	2	4	5

Затраты на перевозку 1 т овощей на 1 км постоянны и равны 20 рублей. Определите план перевозки продукта до потребителей из условия минимизации транспортных расходов.

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

Хранилище	Потребители
	П1	П2	П3	П4
1	140	60	60	160
2	140	120	40	140
3	80	140	140	60
4	100	40	80	100

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

	1	2	3	4	Запасы
1	140	60	60	160	10
2	140	120	40	140	20
3	80	140	140	60	35
4	100	40	80	100	45
Потребности	25	30	40	15

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

∑a = 10 + 20 + 35 + 45 = 110

∑b = 25 + 30 + 40 + 15 = 110

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

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

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

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

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

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

	1	2	3	4	Запасы
1	140	60	60[10]	160	10
2	140	120	40[20]	140	20
3	80[20]	140	140	60[15]	35
4	100[5]	40[30]	80[10]	100	45
Потребности	25	30	40	15

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

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

F(x) = 60*10 + 40*20 + 80*20 + 60*15 + 100*5 + 40*30 + 80*10 = 6400

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₃ = 60; 0 + v₃ = 60; v₃ = 60

u₂ + v₃ = 40; 60 + u₂ = 40; u₂ = -20

u₄ + v₃ = 80; 60 + u₄ = 80; u₄ = 20

u₄ + v₁ = 100; 20 + v₁ = 100; v₁ = 80

u₃ + v₁ = 80; 80 + u₃ = 80; u₃ = 0

u₃ + v₄ = 60; 0 + v₄ = 60; v₄ = 60

u₄ + v₂ = 40; 20 + v₂ = 40; v₂ = 20

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят: F(x) = 60*10 + 40*20 + 80*20 + 60*15 + 100*5 + 40*30 + 80*10 = 6400.

Из 1-го овощехранилища необходимо весь груз направить к 3-му потребителю.

Из 2-го овощехранилища необходимо весь груз направить к 3-му потребителю.

Из 3-го овощехранилища необходимо груз направить к 1-му потребителю (20), к 4-му потребителю (15).

Из 4-го овощехранилища необходимо груз направить к 1-му потребителю (5), ко 2-му потребителю (30), к 3-му потребителю (10).

Задача 4.

Для кормления птицы используется 2 типа корма, содержащие питательные вещества-витамины А, В и С. Содержание числа единиц витаминов в 1 кг каждого вида корма и необходимый минимум их приведен в таблице (цифры условные).

Витамины	Необходимый минимум витамина	Число единиц витамина в 1 кг корма
		1-ый корм	2-ой корм
А	9	3	1
В	8	1	2
С	12	1	6

Стоимость 1-го кг корма 1-го и 2-го типа соответственно 4 и 6 руб. необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ (витаминов) было бы не менее установленных пределов.

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

Пусть х₁ – количество корма 1. Х₂ – количество корма 2.

Тогда ограничения на витамин А:

Ограничения на витамин В:

Ограничения на витамин С:

Стоимость дневного рациона (корм 1 и корм 2) составит:

Составим прямую задачу задачу:

Составим двойственную задачу:

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

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

В 1-м неравенстве смысла (≥) вводим базисную переменную x₃ со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x₄ со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.

Умножим все строки на (-1) и будем искать первоначальный опорный план.

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,-9,-8,-12)

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

Базис	B	x1	x2	x3	x4	x5
x3	-9	-3	-1	1	0	0
x4	-8	-1	-2	0	1	0
x5	-12	-1	-6	0	0	1
F(X0)	0	4	6	0	0	0

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 3-ая строка, а переменную x₅ следует вывести из базиса. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x₂ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-6).

Базис	B	x1	x2	x3	x4	x5
x3	-9	-3	-1	1	0	0
x4	-8	-1	-2	0	1	0
x5	-12	-1	-6	0	0	1
F(X0)	0	4	6	0	0	0
θ		4 : (-1) = -4	6 : (-6) = -1	-	-	-

Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5
x3	-7	-17/6	0	1	0	-1/6
x4	-4	-2/3	0	0	1	-1/3
x2	2	1/6	1	0	0	-1/6
F(X0)	-12	3	0	0	0	1

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

B	x 1	x 2	x 3	x 4	x 5
-9-(-12 • -1):-6	-3-(-1 • -1):-6	-1-(-6 • -1):-6	1-(0 • -1):-6	0-(0 • -1):-6	0-(1 • -1):-6
-8-(-12 • -2):-6	-1-(-1 • -2):-6	-2-(-6 • -2):-6	0-(0 • -2):-6	1-(0 • -2):-6	0-(1 • -2):-6
-12 : -6	-1 : -6	-6 : -6	0 : -6	0 : -6	1 : -6
0-(-12 • 6):-6	4-(-1 • 6):-6	6-(-6 • 6):-6	0-(0 • 6):-6	0-(0 • 6):-6	0-(1 • 6):-6

План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

Среди отрицательных значений базисных переменных выбираем наибольший по модулю. Ведущей будет 1-ая строка, а переменную x₃ следует вывести из базиса. Минимальное значение θ соответствует 5-му столбцу, т.е. переменную x₅ необходимо ввести в базис.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (^-1/₆).

Базис	B	x1	x2	x3	x4	x5
x3	-7	-25/6	0	1	0	-1/6
x4	-4	-2/3	0	0	1	-1/3
x2	2	1/6	1	0	0	-1/6
F(X0)	-12	3	0	0	0	1
θ		3 : (-25/6) = -11/17	-	-	-	1 : (-1/6) = -6