Задача№1 (стр. 1 )

Задача№1

Необходимо найти максимальное значение целевой функции F = 4X1+5X2 → max, при системе ограничений:

10x1+5x2≤310	(1)
5x1+4x2≤120	(2)
3x1+13x2≤250	(3)
x1≥0	(4)
x2≥0	(5)

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

Границы области

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

Целевая функция F(x) → max

Рассмотрим целевую функцию задачи F = 4X1+5X2 → max.
Построим прямую, отвечающую значению функции F = 0: F = 4X1+5X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб

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

Прямая F(x) = const пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:
5x1+4x2≤120
3x1+13x2≤250
Решив систему уравнений, получим: x1 = 10.566, x2 = 16.7925
Откуда найдем максимальное значение целевой функции:
F(X) = 4*10.566 + 5*16.7925 = 126.23

Задача№2

Необходимо найти минимальное значение целевой функции F = 59X1+11X2 → min, при системе ограничений:

x1+3x2≥9	(1)
5x1+2x2≥9	(2)
2x1+8x2≥8	(3)
3x1+4x2≥49	(4)
x1≥0	(5)
x2≥0	(6)

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

Границы области

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

Целевая функция F(x) → min

Рассмотрим целевую функцию задачи F = 59X1+11X2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 59X1+11X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Равный масштаб

Область допустимых значений неограниченна.
3x1+4x2≥49
=
Решив систему уравнений, получим: x1 = 0, x2 = 12.25
Откуда найдем значение целевой функции:
F(X) = 59*0 + 11*12.25 = 134.75

Задача№3

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

	1	2	3	4	Запасы
1	2	5	8	5	226
2	8	2	4	2	240
3	2	4	3	6	84
4	2	4	3	5	70
Потребности	292	170	111	40

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

∑a = 226 + 240 + 84 + 70 = 620

∑b = 292 + 170 + 111 + 40 = 613

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

	1	2	3	4	5	Запасы
1	2	5	8	5	0	226
2	8	2	4	2	0	240
3	2	4	3	6	0	84
4	2	4	3	5	0	70
Потребности	292	170	111	40	7

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

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

	1	2	3	4	5	Запасы
1	2[226]	5	8	5	0	226
2	8	2[170]	4[23]	2[40]	0[7]	240
3	2[66]	4	3[18]	6	0	84
4	2	4	3[70]	5	0	70
Потребности	292	170	111	40	7

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

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

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

F(x) = 2*226 + 2*170 + 4*23 + 2*40 + 0*7 + 2*66 + 3*18 + 3*70 = 1360

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

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

	v1=2	v2=1	v3=3	v4=1	v5=-1
u1=0	2[226]	5	8	5	0
u2=1	8	2[170]	4[23]	2[40]	0[7]
u3=0	2[66]	4	3[18]	6	0
u4=0	2	4	3[70]	5	0

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

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

F(x) = 2*226 + 2*170 + 4*23 + 2*40 + 0*7 + 2*66 + 3*18 + 3*70 = 1360

Задача№4

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