Исследования операций в экономике

Задание 1. Решить задачу линейного программирования

линейный программирование симплекс задача.

F = 4×2 + x4 max.

x1 + x2 + x3 = 11.

• 2x1 — 3×2 — x4 = 1
• -x1 + x2 + x5 = - 3, x1, x2, x3, x4, x5 0

Решение: Выразим из уравнений х3 = - х1 — х2 + 11 (*).

х4 = 2×1- 3×2 — 1 (**).

х5 = х1 — х2 — 3 (***).

Подставим х4 в F.

F = 2×1 + x2 — 1.

Из условий неотрицательности х3×4×5 получаем задачу ЛП :

F = 2×1 + x2 — 1 > max.

• — х1 — х2 + 11 0
• 2х1- 3×2 — 1 0

х1 — х2 — 3 0, х1 0, х2 0,.

или в виде (перенесём числа вправо и умножим на -1).

F = 2×1 + x2 — 1 > max.

х1 + х2 11.

2х1 — 3×2 1 (1).

х1 — х2 3, х1 0, х2 0.

Решим графически. Построим область допустимых решений (ОДP).

Для этого построим прямые (заменим в системе (1) знак неравенства на =).

х1 + х2 = 11 (1).

2х1 — 3×2 = 1 (2).

х1 — х2 = 3 (3).

Т.к. все неравенствa-ограничения можно записать в виде х2 …,.

то штрихуем ниже прямых .

ОДР — треугольник ABС. Проводим вектор-градиент, (его координаты — коэффициенты целевой функции (2; 1), малиновая стрелка), он указывает направление максимизации F (X). Поскольку задача на максимум, двигаем линию уровня (красный пунктир) в направлении градиента до последнего касания ОДР в угловой точке С.

Она получена при пересечении прямой (1) с ОХ1, подставим в уравнение прямой (1) х2* = 0, получим х1* = 11.

Максимум ЦФ :

Fmax = 2×1* + x2* - 1 = 2*11 + 0 — 1 = 21.

Найдём х3×4×5 по формулам (*)-(**) и проверим неотрицательность х3* = - х1* - х2* + 11 = - 11 — 0 + 11 = 0 0.

х4* = 2×1* - 3×2* - 1 = 22 — 1 = 21 0.

х5* = х1* - х2* - 3 = 11 — 3 = 8 0.

Ответ: х1* = 11; х2* = 0; х3* = 0; х4* = 21; х5* = 8; Fmax = 21.