Задача 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.