I. Общая задача ЛП

z – целевая функция

c = (c ₁, …, c_n) – вектор целей

A = (a_ij) _{m x n} – матрица задачи (матрица условий)

b = (b ₁, …, b_m) – вектор ограничений (вектор правых условий)

x = (x ₁, …, x_n) – план задачи (решение задачи)

Условие x_j ≥ 0 – условие неотрицательности переменных

Множество x, удовлетворяющих всем ограничениям называется множеством допустимых решений, обозначается X. План, на котором достигается оптимум целевой функции (минимум/максимум) называется решением задачи (оптимальный план), обозначается x ^*. X ^* – множество решений задачи.

Решить общую задачу ЛП означает, найти хотя бы один оптимальный план и вычислить оптимальное значение.

Частные задачи ЛП

Скалярная форма	Матричная форма	Векторная форма
II. Стандартная задача ЛП (задача планирования производства)
III. Каноническая задача ЛП (транспортная задача)
IV. Основная задача ЛП

Все виды задач ЛП эквивалентны: существуют однозначные правила перехода от одного вида задачи к другому и решая последнюю задачу и вспоминая правила перехода, мы можем написать решение исходной задачи, не решая ее.

Правила перехода

1)

2)

3)

x_{n + i} – дополнительные переменные, (насколько недоиспользовано ограничение)

4)

5)

Пусть a_{i 1} ≠ 0

6) Пусть

7) Пусть x_j – свободная ~ – любую свободную переменную можно представить в виде разности двух неотрицательных переменных.

11. Графический анализ линейных моделей.

m = 3

1) Строим границы множества решений, которые соответствуют неравенствам (прямые: )

2) Находим полуплоскости, соответствующие каждому ограничению (метод пробной точки)

3) Находим многоугольник допустимых решений, как пересечение найденных полуплоскостей. Полученную область заштриховать. Возможные варианты:

a. X – многоугольник

b. X – пустое множество

c. X – неограниченное многоугольное множество

4) Находим координаты вектора градиента целевой функции (вектор целей – вектор нормали к линиям уровня)

5) Строим прямую (перпендикулярно вектору цели), которая соответствует линии уровня для z ₀ = 0.

Затем перемещаем прямую в направлении вектора цели (в случае задачи на min – в противоположном направлении) до тех пор, пока прямая имеет общие точки с множеством допустимых решений. Крайнее положение – ответ.

6) Вычисляем координаты крайней точки, как пересечение соответствующих прямых и вычисляем значение целевой функции в этой точке.

Ответ: