Задача 1.
Решите графическим методом задачу линейного программирования. Найти максимум и минимум функции при заданных ограничениях.
Решение:
Найдем оптимальное решение задачи , математическая модель которой имеет вид
Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.2.2).
(1) – (2) – (3) –
(4) –
Рис.1. Графическое решение задачи 1
Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (3), получим , что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную левее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является треугольник CFH.
Целевую прямую можно построить по уравнению
Строим вектор из точки (0;0) в точку (1,1). Точка C– это последняя вершина области допустимых решений CFH, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому C– это точка максимума ЦФ. Определим координаты точки C из системы уравнений прямых ограничений (3) и (2)
,
Максимальное значение ЦФ равно
Задача 2.
Решите симплекс-методом задачи линейного программирования.
Решение:
Приведем ЗЛП к каноническому виду:
Все дальнейшие расчеты поместим в симплекс-таблицу :
Номер симплекс-таблицы
Базис
Cj
Ci
В
-6
-4
4
0
0
Q
A1
A2
A3
A4
A5
0
A4
0
1
-1
-1
-1
1
0
-
A5
0
1
-2
-1
1
0
1
1
-
0
6
4
-4
0
0
-
1
A4
0
2
-3
-2
1
0
1
-
A3
4
1
-2
-1
0
1
1
-
-
4
10
0
0
0
4
-
В сисмплекс-таблице 1 получен оптимальный опорный план, т.к. все оценки . Оптимальные значения переменных . Максимальное значение функции равно 4.
Приведем ЗЛП к каноническому виду:
За базисные неизвестные примем , за свободные неизвестные - . Начальный опорный план имеет вид: (3,0,5,0).
Выразим базисные неизвестные через свободные:
Тогда линейная форма:
Все дальнейшие расчеты поместим в симплекс-таблицу :
Номер симплекс-таблицы
Базис
Cj
Ci
В
0
-38
0
-40
Q
A1
A2
A3
A4
0
A1
0
3
1
4
0
1
?
A3
0
5
0
7
1
2
5/7
-
30
0
38
40
0
-
В сисмплекс-таблице 0 получен оптимальный опорный план, т.к. все оценки . Оптимальные значения переменных . Максимальное значение функции равно 30.