1-10. Построить на плоскости область решений линейных неравенств и геометрически найти максимальное и минимальное значения целевой функции в этой области.
Решение.
Построим область допустимых решений, т.е. решим графически систему неравенств.
1)Границей неравенства 4×1-x2≥6 является прямая 4×1-x2=6 , построим ее по двум точкам:
х1
0 2
х2
-6 2
Произвольная точка (0; 0) не удовлетворяет неравенству4×1-x2≥6 , поэтому областью решения неравенства являются точки, лежащие выше прямой 4×1-x2=6 . Область решения обозначим штриховкой.
2)Границей неравенства 9×1+8×2≤157 является прямая 9×1+8×2=157, построим ее по двум точкам:
х1
0 157/9
х2
157/8 0
Произвольная точка (0; 0) удовлетворяет неравенству 9×1+8×2≤157, поэтому областью решения неравенства будут точки, лежащие ниже прямой 9×1+8×2=157. Объединим полученную полуплоскость с ранее найденными ограничениями. Область решения обозначим штриховкой.
3) Границей неравенства -3×1+11×2≥16 является прямая -3×1+11×2=16, построим ее по двум точкам:
х1
0 -16/3
х2
16/11 0
Произвольная точка (0; 0) не удовлетворяет неравенству-3×1+11×2≥16 , поэтому областью решения неравенства являются точки, лежащие выше прямой -3×1+11×2=16. Объединим полученную полуплоскость с другими ограничениями . Область решения обозначим штриховкой.
Общая часть всех полуплоскостей область АВСDE является областью решений системы линейных неравенств.
Строим вектор-градиент целевой функции FX=x1+x2:
∇F=1;1.
(координаты вектора-градиента – частные производные функции ).
Проводим линию линейной функции перпендикулярно вектору-градиенту.
Для отыскания точки, соответствующей максимальному значению функции, сдвигаем линию уровня параллельно самой себе в направлении, указанном вектором ∇F.
Максимального значения функция достигает в точке: В(5,14)
Для отыскания точки, соответствующей минимальному значению функции, сдвигаем линию уровня параллельно самой себе в направлении, обратном указанному вектором ∇F.
Минимального значения функция достигает в точке: A(2,2) .
Fmin=FА=1∙2+2=4;
Fmax=FВ=1∙5+1*14=19.
Решение:
Fmin=FА=4;
Fmax=FВ=19.
20. Решить задачу с помощью симплекс-метода.
Найти максимум целевой функции при данной системе ограничений.
Решение.
Шаг:1Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3 неотрицательные балансовые переменные s1, s2, s3.
2 x1 +
x2 + 6 x3 +
s1
=
12
(1)
3 x1 + 3 x2 + 9 x3
+
s2
=
27
(2)
2 x1 +
x2 + 2 x3
+
s3 =
6
(3)
x1, x2, x3, s1, s2, s3 ≥ 0Шаг:2Ищем в системе ограничений базисные переменные.Из последней системы ограничений можно выделить базисные переменные s1,s2,s3.
Теперь мы можем сформировать начальную симплекс-таблицу.Шаг:3Начальная симплекс-таблица
БП x1 x2 x3 s1 s2 s3 Решение Отношение
s1 2 1 6 1 0 0 12 12 / 6 = 2
s2 3 3 9 0 1 0 27 27 / 9 = 3
s3 2 1 2 0 0 1 6 6 / 2 = 3
Z 14 6 22 0 0 0 0 —
Итерация 1
БП x1 x2 x3 s1 s2 s3 Решение Отношение
x3 1
3
1
6
1 1
6
0 0 2 2 / 1
3
= 6
s2 0 3
2
0 -3
2
1 0 9 —
s3 4
3
2
3
0 -1
3
0 1 2 2 / 4
3
= 3
2
Z 20
3
7
3
0 -11
3
0 0 -44 —
Итерация 2
БП x1 x2 x3 s1 s2 s3 Решение Отношение
x3 0 0 1 1
4
0 -1
4
3
2
—
s2 0 3
2
0 -3
2
1 0 9 —
x1 1 1
2
0 -1
4
0 3
4
3
2
—
Z 0 -1 0 -2 0 -5 -54 —
Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.Ответ:
Оптимальное значение функции Z(x)= 54
достигается в точке с координатами:
x1= 3
2
x2= 0
x3= 3
2
s1= 0
s2= 9
s3= 0
30. Найти оптимальные планы транспортных задач:
30. На трех железнодорожных станциях скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции . На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Стоимости перегона вагонов задаются матрицей
.
Составьте такой план перегонок вагонов, чтобы общая стоимость была бы минимальной.
Решение.
Шаг:1Проверка на сбалансированность
Общее число запасов на складах : 360 ; Общая потребность : 360
