5.2 Задача линейного программирования

Постановка задачи линейного программирования. Задачи ли­нейного программирования (ЗЛП) - простейший тип оптимизационных задач. Постановка данной задачи выглядит следующим образом.

Имеется множество переменных X = (х₁ , х₂,..., х_п). Целевая функ­ция линейно зависит от управляемых параметров:

Имеются ограничения, которые представляют собой линейные фор­мы:

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

F(x₁, x₂.,. ., х_п) = max(c_lx₁ + с₂х₂ +... + с_пх_п)

при условии, что точка (x₁ , x₂ ,..., х_п) принадлежит некоторому множе­ству D которое определяется системой линейных неравенств

• 

Любое множество значений, которое удовлетворяет системе неравенств задачи линейного программирования, явля­ется допустимым решением данной задачи.

Задачу линейного программирования удобно представлять в вектор­ной форме, тогда она будет выглядеть:

max F(x) = max (c^Т x),

АХ≤ Р₀,

Х≥ 0,

где с = (c₁ , c₂,..., с_п) представляет собой n - мерный вектор, составлен­ный из коэффициентов целевой функции, причем с^т-транспонированная вектор-строка; Х = (x₁ , x₂ ,..., х_п) – n-мерный вектор переменных решений; Р₀ – m-мерный вектор свободных членов ограничений; матрица А размером (m х п) - матрица, составленная из коэффициен­тов всех линейных ограничений.

Простые ЗЛП допускают геометрическую интерпретацию, позво­ляющую непосредственно из графика получить решение и проиллюстри­ровать идею решения более сложных задач линейного программирования.

Каноническая форма задачи линейного программирования. Любую задачу линейного программирования можно свести к некоторой стандартной форме с ограничениями, записанными в виде уравнений. Это достигается путем введения свободных переменных во все огра­ничения. Свободная переменная учитывает разницу между правой и левой частями неравенства. Пусть х_п+1 -дополнительная переменная, которая численно равна

х_п+2 - дополнительная переменная, которая численно равна

и т.д.

В результате получаем новую систему ограничений:

Целевая функция будет иметь вид

max F(x) = max(c^Tx)

при условии

АХ₁ + ВХ₂=Р₀,

Х₁ > 0,

X₁ > 0,

где X₁ - вектор первоначальных переменных; Х₂ - вектор свободных переменных; В - единичная матрица т х п.

Такую форму записи называют канонической формой задачи линей­ного программирования. В канонической форме ограничения записыва­ются в виде равенств.

При записи задачи линейного программирования в стандартной или канонической форме число линейно независимых уравнений, как прави­ло, меньше числа переменных (на практике всегда т < п, где т - число уравнений). Отметим некоторые свойства, касающиеся системы огра­ничений:

1. уравнения линейно независимы, если ни одно из них не может быть получено из остальных путем алгебраических преобразований, т.е. никакие из них не являются следствием остальных;

2. если число независимых уравнений больше числа переменных, то такая система не имеет решения и называется несовместимой;

3. если число независимых уравнений равно числу переменных, то такая система имеет единственное решение, которое либо оптималь­но, если все компоненты положительны, либо недопустимо, если хотя бы одна из компонент отрицательна;

4. если удается найти множество неотрицательных значений Х= (x₁ х₂,..., х_п), которое является решением системы т линейных уравнений с п+т неизвестными, то такое решение называют базисным, а ненуле­вые переменные - базисными переменными.

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

Пусть требуется найти максимум линейной формы

max F(x₁, x₂) = max(x₁ + 2x₂)

при условии

x₁+х₂ ≤120,

0 ≤ х₁ ≤ 100,

0≤ x_2≤75.

Изобразим область, описываемую совокупностью ограничений на плоскости (рисунок 5.1). Переменные х₁ и х₂ неотрицательные, по­этому множество точек, являющихся возможными решениями задачи, находятся в I квадранте. Заменим знак в х₁+ х₂ ≤ 120 на знак равенства, получим уравнение прямой: х₁ + х₂ = 120. Эта прямая делит плоскость на две полуплоскости. Все точки одной полуплоскости удов­летворяют неравенству х_] + х₂ > 120, другой - неравенству х₁ + х₂ < 120.

Построив аналогичные прямые х₁ =100 и х₂ = 75, получим много­угольник, множество точек которого удовлетворяет всем нера­венствам системы ограничений. Этот многоугольник и представляет собой область допустимых решений D.

Из множества точек (х₁ x₂) многоугольника необходимо выбрать такую, в которой функция F(х₁ ,x₂) = (х₁ + 2х₂) принимает максимальное значение.

Рис. 5.1. Геометрическая интерпретация задачи линейного программирования

Для некоторого фиксированного значения F* линейная функ­ция F*(x₁, х₂) = (x₁ + 2х₂) представляет собой прямую линию. Задава­ясь различными значениями F* получим семейство параллельных пря­мых. Увеличение значений линейной функции соответствует перемеще­нию прямой параллельно самой себе вверх. Следовательно, как видно из рисунка 6.1, максимальное значение целевой функции на допустимом множестве точек соответствует прямой, проходящей через точку z пе­ресечения прямых x₁ + х₂= 120 и х₂= 75.

Решив эту систему, получим x₁ = 45. Тогда максимальное значение функции F = max(x₁ + 2x₂) =195.