Контрольная работа по "Высшей математики"

Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (красный цвет), так как ее воздействие на общие затраты является максимальным. В нашем случае такая оценка находится в ячейке а3,b5 (красный цвет), в соответствующую ячейку транспортной таблицы мы должны переместить некоторое количество продукции т.е. загрузить ее. Отметим в транспортной таблице ячейку а3,b5 знаком + . Кроме нее мы пометим знаками – и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков - . Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и - .То есть помеченные знаками клетки должны образовывать цикл.

	= 120	= 80	80	= 70	= 90
= 150	60          +				90       -
= 130	50		80
= 160	10          -	80		70	+

Затем мы определим минимум M из всех элементов, помеченных знаком - , и выбираем одну ячейку где этот минимум достигается. В нашем случае таковой является а3,b1 и обозначает загруженную клетку, которая должна стать свободной. Число М при этом составляет: 0

Переход к новой транспортной таблице разбивается на следующие шаги.

а) В ячейку а3,b5 новой таблицы записывается число M.

б) Ячейка а3,b1 остается пустой.

в) В остальных ячейках, помеченных знаками - или +, число M соответственно вычитается из стоящего в ячейке числа или складывается с ним. Результат вносится в соответствующую ячейку новой таблицы.

г) Непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми.

	= 120	= 80	80	= 70	= 90
= 150	60				80
= 130	50		80
= 160		80		70	10

 

Итерация: 2 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	7	4	-1	3	0	= 0
	5	0	3	3	2	= -2
	6	8	2	3	0	= 0
	= 7	= 8	= 5	= 3	= 0

Ячейка а1,b3, транспортной таблицы, должна загрузиться.

	= 120	= 80	80	= 70	= 90
= 150	70          -		+		80
= 130	50         +		80        -
= 160		80		70	10

 

Ячейка а1,b1 становится свободной. М = 70

	= 120	= 80	80	= 70	= 90
= 150			70		80
= 130	120		10
= 160		80		70	10

 

Итерация: 3 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	1	4	4	3	0	= 0
	5	-1	3	2	1	= -1
	7	8	3	3	0	= 0
	= 6	= 8	= 4	= 3	= 0

Ячейка а2,b2, транспортной таблицы, должна загрузиться.

	= 120	= 80	80	= 70	= 90
= 150			70         +		80         -
= 130	120	+	10         -
= 160		80         -		70	10         +

 

Ячейка а2,b3 становится свободной. М = 10

	= 120	= 80	80	= 70	= 90
= 150			80		70
= 130	120	10
= 160		70		70	20

 

Итерация: 4 Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

	0	4	4	3	0	= 0
	5	6	1	3	2	= -2
	6	8	3	3	0	= 0
	= 7	= 8	= 4	= 3	= 0

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

	= 120	= 80	80	= 70	= 90
= 150			80      4		70      0
= 130	120     5	10        6
= 160		70        8		70      3	20      0

Общие затраты на перевозку всей продукции, для оптимального плана составляют: Р = 1750

 

Задача № 4

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

F=3x1+2x2 → max,

+  ≤ 11

+ ≤ 17

x1  ≥ 0, x2 ≥ 0,

x1, x2 – целые

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

 

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

 

3). Рассмотрим целевую функцию задачи F = 3x1+2x2 → max.

Построим прямую, отвечающую значению функции F = 0: F = 3x1+2x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3; 2). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

 

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:

x1+6x2=11

5x1+3x2=17

Решив систему уравнений, получим: x1 = 2.5556, x2 = 1.4074

Откуда найдем максимальное значение целевой функции: F(X) = 3*2.5556 + 2*1.4074 = 10.4815

Решение получилось не целочисленным.

Множество допустимых решений задачи с отмеченными на нем целочисленными точками представлено на рис. 5.

Перемещение линии уровня целевой функции F(X) в направлении, задаваемом ее градиентом, показывает, что наибольшее значение F(X)=9 она примет в точке (3, 0).

 

Задача № 5

Решить задачу целочисленного программирования, в которой как целевая функция, так и функции в системе ограничений являются линейными. На предприятии производятся “изделия” четырех наименований, обладающие различной ценностью. В производственном процессе используются три вида сырья.

               Норма расхода ресурсов на  единицу изделия

	Изд 1	Изд 2	Изд 3	Изд 4	Запас ресурсов
Ресурс 1	5	10	15	20	150
Ресурс 2	20	15	10	5	170
Ресурс 3	15	9	4	17	190
Ценность	6,5	8	14	10