103. Приведите к канонической форме задачу линейного программирования:

z = x3 + 2x1 + 3x2 → max

x1 + 2x2 + 3x3 ≥ 8

x1 + 5x2 + x3 ≥ 4

x1 + 2x2 + 7x3 = 5

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0

Введем новые переменные

x4 = x1 + 2x2 + 3x3 − 8 ≥ 0

x5 = x1 + 5x2 + x3 − 4 ≥ 0

и используем их в первых двух неравентсвах, приведя задачу к канонической форме:

z = x3 + 2x1 + 3x2 → max

x1 + 2x2 + 3x3 = 8+x4

x1 + 5x2 + x3 = 4+x5

x1 + 2x2 + 7x3 = 5

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0

104. Приведите пример задачи линейного программирования и постройте для нее двойственную задачу.

Задача:

Двойственная задача:

Тут надо составить следующие элементы:

А=в=с=.

105. Сформулируйте основные теоремы двойственности.

Теорема1: если исходная задача имеет оптимально решение , то и двойственная ей также имеет оптимальтное решение при этом оптимальные значения целевых ф-й обеих здачач раны т. е. zmax=Tmin

Теорема2: достаточный признак оптимизации: если х₀ и у₀ –допустимые решения пары двойственных задач и при этом z(x₀)=T(y₀), то х₀ и у₀ –оптимальные решения той и другой задачи. T(y₀)≥Z(x₀).

Теорема3:оснятии решения двойственной задачи с последней симплексной таблицы исходной задачи: у₀=а_0Е+с_{Е ;} а-вектор индексной строки, координаты которого соотв базисным перемененным исходной таблицы, с-вектор с теми же коорд целевой ф-ии соответственно.

106. Как по графическому решению задачи линейного программирования найти решение двойственной задачи. Приведите пример.