Контрольная работа по "Математике". 59

Задание 1.

Дана задача линейного программирования

при ограничениях:

      

Графическим методом найти оптимальные решения при стремлении целевой функции к максимальному и минимальному значениям.

Значения коэффициентов целевой функции и системы ограничений

Значения	9 вариант
	3
	0
	-3
	2
	-6
	2
	1
	14
	3
	-4
	0
	0
	1
	6

 

 

Решение:

Найдем область допустимых решений (ОДР). Для этого построим граничные прямые:

Определим полуплоскости, определенные неравенствами системы (подставим т. О (0, 0)) для (1) неравенства полуплоскость лежит ниже прямой l1, для (2) неравенства полуплоскость лежит ниже прямой l2, для (3) неравенства возьмем т. F (0, 1), тогда полуплоскость лежит выше прямой l3, для (4) неравенства полуплоскость лежит ниже прямой l4. Пересечение всех полуплоскостей дает область BDGH.

Строим вектор-градиент целевой функции и одну из линий уровня: , это будет ось OY.

Будем перемещать линию уровня в направлении вектора вверх и вниз до тех пор, пока линия уровня и ОДР не будут иметь одну общую точку.

Получим 2 точки: т. B(0,0) и т. H= l2 l3

т.Н (5,09; 3,82)

Следовательно, в т. B(0,0) функция Z достигает min.

Z (В) = 3*0 = 0

В т. Н (5,09; 3,82) функция Z достигает max: Z (Н) = 3*5,09 = 15,27.

 

 

Задание 2.

Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице.

Расходы и суточные запасы исходных продуктов

Исходный продукт	Расход  продуктов на 1 т краски		Суточный запас, т
	Краска Н	Краска В
Пигмент
Олифа

Изучение рынка сбыта показало, что суточный спрос на краску для наружных (внутренних) работ никогда не превышает т в сутки. Цена продажи 1 т краски для наружных работ ден. ед.

Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был максимален?

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

Значения	Вариант 9
	2
	3
	1
	1
	7
	2
	1
	10
	0
	1
	6

 

Примечание. Если по условию задания спрос на краску Н (В) работ не превышает т в сутки, то в математической модели задачи следует принять, что коэффициент системы ограничений ( ) равен 1 (0), а при неизвестном значении краски для В (Н) работ ( ) равен 0 (1).

Решение:

Введем обозначения: Пусть х1 – количество краски Н, х2 – количество краски В, тогда составим математическую модель задачи:

Решим ее графическим методом:

Строим область ОДР:

                                 

Определим полуплоскости, подставив т. О (0, 0). В результате получим область АВСEД.

Строим вектор-градиент

 и одну из линий уровня:

 

х1	0	3
х2	0	-2

  .

 

 

Будем перемещать ее вверх в направлении вектора . Получим точку C=l1 l2

В этой т. C функция Z достигает max Z(C)=2*1+3*6=20.

Ответ: чтобы доход был max, нужно производить краску В 1 т. в сутки, краску H 6 т. в сутки.

 

Задание 3.

Составить математическую модель и решить задачу симплексным методом.

В производстве пользующихся спросом двух изделий, А или В, принимают участие 3 цеха. На изготовление одного изделия А первый цех затрачивает час, второй цех - час, третий цех - час. На изготовление одного изделия В первый цех затрачивает час, второй цех - час, третий цех - час. На производство обоих изделий первый цех может затратить не более час, второй цех не более час, третий цех – не более час.

От реализации одного изделия А фирма получает доход руб., изделие В - руб.

Определить максимальный доход от реализации всех изделий А и В.

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

Значения	Вариант 9
	7
	7
	8
	5
	2
	1
	347
	300
	350
	11
	7

Решение:

Введем обозначения:

Пусть x1 – количество изделий А, x2 – количество изделий В.

Изделие/цех	I	II	III
A	7x1	7x1	8x1
B	5x2	2x2	x2

 

Тогда получаем систему ограничений

Перейдем к каноническому виду системы ограничений:

Строим таблицу:

БП		11	7	0	0	0	0
		х1	х2	х3	х4	х5	вi
0	х3	7	5	1	0	0	347	I
0	х4	7	2	0	1	0	300	II
0	х5	8	1	0	0	1	350	III
Δ		-11	-7	0	0	0	0

 

т.к. среди Δ есть отрицательные значения, то решение можно улучшить. Выбираем Δ=-11, это первый столбец, найдем разрешающую строку:

Это вторая строка.

Получим разрешающий элемент 7. Построим новую таблицу. Для этого II строку делим на 7, получим II-н (новую строку). Для получения I-н нужно из I строки – II-н*7. Для получения III-н нужно из III строки – II-н*8.

Получим следующую таблицу:

БП		11	7	0	0	0	0
		х1	х2	х3	х4	х5	вi
0	X3	0	3	1	-1	0	47
11	X1	1	2/7	0	1/7	0	42 6/7
0	X5	0	-1 2/7	0	-1 1/7	1	7 1/7
Δ		0	-3 6/7	0	1 4/7	0	471 3/7

 

т.к. среди Δ есть отрицательные значения, то решение можно улучшить. Выбираем Δ=-3 6/7, это второй столбец, найдем разрешающую строку:

Это первая строка.

Получим разрешающий элемент 3. Построим новую таблицу. Для этого I строку делим  на 3, получим I-н (новую строку). Для получения II-н нужно из II строки – I-н*2/7. Для получения III-н нужно к III строке + I-н* 
1 2/7.

Получим следующую таблицу:

 

 

 

БП		11	7	0	0	0	0
		х1	х2	х3	х4	х5	вi
7	X2	0	1	1/3	- 1/3	0	15 2/3
11	X1	1	0	-0	1/4	0	38 3/8
0	X5	0	0	3/7	-1 4/7	1	27 2/7
Δ		0	0	1 2/7	2/7	0	531 6/7

 

т.к. все Δ положительные либо 0, значит получено решение задачи.

Из таблицы следует:

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

Задание 4.

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

 

	40	20	40
30
25
15
30

 
Значение коэффициентов распределительной таблицы.

Значения	Вариант 9
	2
	4
	3
	2
	5
	2
	4
	1
	4
	5
	3
	5

Решение:

Решим задачу методом Северо-Западного угла

аi \ bj	40	20	40
30	30 2	- 4	- 3
25	10 2	15 5	- 2
15	- 4	5 1	10 4
30	- 5	- 3	30 5

Так сумма ai = 30 + 25 + 15 + 30 = 100 и сумма bj = 40 + 20 + 40 = 100, то модель закрытая.

Затраты на перевозки = 30*2 + 10*2 + 15*5 + 5*1 + 10*4 + 30*5 = 350 (ден.ед).

План построен базисный. Т.к. число занятых клеток m+n-1= 3 + 4 – 1 = 6. Проверим, получили ли мы оптимальный план с помощью метода потенциалов.

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

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

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v2 = 5; 0 + v2 = 5; v2 = 5

u3 + v2 = 1; 5 + u3 = 1; u3 = -4

u3 + v3 = 4; -4 + v3 = 4; v3 = 8

u4 + v3 = 5; 8 + u4 = 5; u4 = -3

 

 

 

	v1=2	v2=5	v3=8
u1=0	2[30]	4	3
u2=0	2[10]	5[15]	2
u3=-4	4	1[5]	4[10]
u4=-3	5	3	5[30]

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

(1;2): 0 + 5 > 4; ∆12 = 0 + 5 - 4 = 1

(1;3): 0 + 8 > 3; ∆13 = 0 + 8 - 3 = 5

(2;3): 0 + 8 > 2; ∆23 = 0 + 8 - 2 = 6

max(1,5,6) = 6

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[15][-]	2 [+]	25
3	4	1[5] [+]	4[10][-]	15
4	5	3	5[30]	30
Потребности	40	20	40

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[5]	2[10]	25
3	4	1[15]	4	15
4	5	3	5[30]	30
Потребности	40	20	40

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

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

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v2 = 5; 0 + v2 = 5; v2 = 5

u3 + v2 = 1; 5 + u3 = 1; u3 = -4

u2 + v3 = 2; 0 + v3 = 2; v3 = 2

u4 + v3 = 5; 2 + u4 = 5; u4 = 3

	v1=2	v2=5	v3=2
u1=0	2[30]	4	3
u2=0	2[10]	5[5]	2[10]
u3=-4	4	1[15]	4
u4=3	5	3	5[30]

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

(1;2): 0 + 5 > 4; ∆12 = 0 + 5 - 4 = 1

(4;2): 3 + 5 > 3; ∆42 = 3 + 5 - 3 = 5

max(1,5) = 5

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

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

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5[5] [-]	2[10][+]	25
3	4	1[15]	4	15
4	5	3 [+]	5[30][-]	30
Потребности	40	20	40

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

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

 

	1	2	3	Запасы
1	2[30]	4	3	30
2	2[10]	5	2[15]	25
3	4	1[15]	4	15
4	5	3[5]	5[25]	30
Потребности	40	20	40

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

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

u2 + v1 = 2; 2 + u2 = 2; u2 = 0

u2 + v3 = 2; 0 + v3 = 2; v3 = 2

u4 + v3 = 5; 2 + u4 = 5; u4 = 3

u4 + v2 = 3; 3 + v2 = 3; v2 = 0

u3 + v2 = 1; 0 + u3 = 1; u3 = 1

	v1=2	v2=0	v3=2
u1=0	2[30]	4	3
u2=0	2[10]	5	2[15]
u3=1	4	1[15]	4
u4=3	5	3[5]	5[25]

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

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

F(x) = 2*30 + 2*10 + 2*15 + 1*15 + 3*5 + 5*25  = 265

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

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

Из 2-го склада необходимо груз направить в 1-й магазин (10), в 3-й магазин (15)

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

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

 Задание 5.

Решить транспортную задачу. Заданы мощности поставщиков аj (j = 1, 2, 3), емкости потребителей bj (j = 1, 2, 3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

bj	25	19	21
40	5	3	6
17	2	1	2
23	7	4	8