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

Пусть требуется найти неотрицательные значения переменных Х₁, Х₂, …, Х_n, для которых функция цели принимает максимальное значение

f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n ® max

при ограничениях

а₁₁Х₁ + а₁₂Х₂ + …+ а_1nХ_n £ b₁,

а₂₁Х₁ + а₂₂Х₂ + …+ а_2nХ_n £ b₂,

………………………………..

а_m1Х₁ + а_m2Х₂ + …+ а_mnХ_n £ b_m,

Х_j ³ 0, (j = ).

 

Поскольку в ограничениях левая часть меньше, чем правая (или равна ей), чтобы перейти к строгому равенству, необходимо к левой части каждого неравенства добавить соответствующую переменную.

Найти максимум функции цели

f(x) = C₁ Х₁ + C₂Х₂ + …+ C_nХ_n + …+ 0×Х_n+1 + …+ 0×Х_n+m ® max

при ограничениях

 

 

а₁₁Х₁ + а₁₂Х₂ + …+ а_1nХ_n + Х_n+1 = b₁,

а₂₁Х₁ + а₂₂Х₂ + …+ а_2nХ_n + Х_n+2 = b₂,

……………………………………………….

а_m1Х₁ + а_m2Х₂ + …+ а_mnХ_n + Х_n+m = b_m,

Х_j ³ 0, (j = ).

Пример. Записать следующую задачу в канонической форме:

f(x) = –X₁ + 2X₂ – X₃ + X₄® min,

3X₁ – X₂ + 2X₃ + 2X₄ £ 10,

X₁ + 2X₂ + X₃ – X₄ ³ 8,

2X₁ – X₂ – X₃ + X₄ £ 6,

–X₁ + 3X₂ + 5X₃ – 3X₄ = 15,

X_j ³ 0, (j = 1 ¸ 4).

Для записи задачи в канонической форме поменяем знаки у всех коэффициентов функции цели на противоположные. Тогда задача будет заключаться в нахождении максимума целевой функции. Для приведения ограничений – неравенств к системе уравнений необходимо приравнять левые и правые части ограничений путем введения дополнительных переменных. Если левая часть ограничения меньше, чем правая, необходимо добавить дополнительную переменную, если же левая часть ограничения больше, из нее следует вычесть некоторое, пока неизвестное, значение.

 

f(x) = Х₁ – 2Х₂ + Х₃ – Х₄ + 0×Х₅ + 0×Х₆ + 0×Х₇ ® max,

3X₁ – X₂ + 2X₃ + 2X₄ + X₅ = 10,

X₁ + 2X₂ + X₃ – X₄ – X₆ = 8,

2X₁ – X₂ – X₃ + X₄ + X₇ = 6,

–X₁ + 3X₂ + 5X₃ – 3X₄ = 15,

X_j ³ 0.

 

Свойства задачи линейного программирования:

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

2. В одной из вершин многогранника решений целевая функция принимает максимальное значение (при условии, что функция ограничена сверху на множестве планов).

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

 

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

Рассмотрим следующую задачу: найти такие значения переменных Х₁ и Х₂, которые максимизируют функцию цели

f(x) = C₁ × Х₁ + C₂ × Х₂ ® max (4.14)

при выполнении ограничений

а_i1 × Х₁ + а_i2 × Х₂ £ b_i; (i = ); (4.15)

условие неотрицательности Х₁ ³ 0, Х₂ ³ 0. (4.16)

Каждое неравенство 2 и 3 системы ограничений геометрически представляет собой полуплоскость с граничными прямыми:

а_i1 × Х₁ + а_i2 × Х₂ = b_i (i = ),

- оси координат (решение

получаем в 1 квадранте).

 

В том случае, если система неравенств 2 и 3 совместна, то область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. А так как множество точек пересечения данных полуплоскостей – выпуклое, то область допустимых решений задачи 1 – 3 есть выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получают из исходной системы ограничений заменой знаков неравенств на знаки точных равенств. Таким образом, исходная задача линейного программирования состоит в нахождении такой точки многоугольника решений, в которой функция цели f(x) принимает максимальное значение. Эта точка существует тогда, когда многоугольник решений не пуст и функция цели ограничена сверху.

При указанных условиях в одной из вершин многоугольника функция цели принимает максимальное значение. Для определения данной вершины строится вектор-нормаль с координатами – коэффициентами функции цели . Перпендикулярно вектору-нормали построим линию уровня C₁ × Х₁ + C₂ × Х₂ = h (где h – некоторое число, которое подбирается таким, чтобы эта линия уровня проходила через многоугольник решений). Будем передвигать линию уровня в направлении вектора–нормали до тех пор, пока она не дойдет до последней общей точки с многоугольником решений. Координаты этой точки и определяют оптимальный план – решение задачи.

Координаты этой точки Анаходятся следующим образом: решается система уравнений, которые соответствуют линиям-ограничениям, на пересечении которых эта точка находится. Подставляя значения координат этой точки в функцию цели, получаем максимальное значение целевой функции. Для нахождения минимума функции цели линия уровня передвигается не в направлении вектора-нормали, а в противоположном направлении.

При нахождении решения задачи 4.14 – 4.16 возможны следующие случаи:

1. Единственное оптимальное решение – в точке А функция цели принимает максимальное значение

Х₂

 

А

- линия уровня

 

С₂ (f(х) ® max)

f(х) = 0 - область

вектор- допустимых значений

нормаль 0 С₁ Х₁

 

2. Множество точек на отрезке DВ – оптимальное решение

Х₂ линия уровня (f(х) ® min)

	в любой точке этого отрезка функция цели принимает минимальное значение. В этом случае функция цели пропорциональна одному из ограничений.

 

A

 

D

 

В

0 Х₁

 

3. Функция цели не ограничена сверху на множестве допустимых решений

Х₂

 

 

- линия уровня (f(х)_max = + ¥)

 

 

0 Х₁

4. Система ограничений задачи несовместна. Условия противоречивы. Многоугольник решений пуст. Решения нет.

Х₂

 

 

Х₁

 

Пример. Найти решение задачи графическим и аналитическим методами:

 

f(x) = 2X₁ + X₂ ® max,

–2X₁ + X₂ £ 2,

X₁ + X₂ £ 4,

X₁ – X₂ £ 1,

X₁ ³ 0, X₂ ³ 0.

 

 

Решение.

 

Построим прямые, уравнения которых получаем в результате замены в системе ограничений знаков неравенств на знаки точных равенств. Получаем уравнения прямых линий на плоскости. Для того, чтобы провести прямую линию, достаточно знать координаты двух точек. Проведем линию (1), соответствующую первому ограничению. Для этого присвоим переменной Х₂ некоторое значение, например ноль, и определим значение переменной Х₁, найдем координаты первой точки (-1; 0). Приравняв нулю переменную Х₁, найдем значение переменной Х₂ – координаты второй точки (0; 2). Для того, чтобы определить, с какой стороны от проведенной линии находится область допустимых значений, необходимо подставить в неравенство координаты какой-нибудь точки пространства, например начала координат (Х₁ = 0, Х₂ = 0). Полученное значение – ноль, меньше чем два (правая часть ограничения), а значит, точка начала координат принадлежит искомой полуплоскости. Повторим построения для всех остальных ограничений задачи и получим многоугольник решений ОDАВЕ. Построим вектор-нормаль, выходящий из начала координат в направлении точки с координатами – коэффициентами функции цели (Х₁ = 2, Х₂ = 1) или пропорциональными этим координатам (Х₁ = 1, Х₂ = 0,5). Линия уровня (соответствующая функции цели) строится перпендикулярно вектору-нормали или же функция цели приравнивается какому-либо числу, например f(x) = 2X₁ + X₂ = 2 и проводится соответствующая линия. Передвинем линию уровня в направлении, указанном вектором. В результате находим точку А, в которой целевая функция принимает максимальное значение. Находим координаты этой точки. Для этого решим систему уравнений, которые соответствуют прямым, на пересечении которых находится точка А:

X₁ + X₂ = 4,

X₁ - X₂ = 1.

Проведем сложение двух уравнений, получим

2X₁ = 5, откуда X₁ = 2,5.

Вычтем из первого уравнения второе, получим

2X₂ = 3, откуда X₂ = 1,5.

Вычислим значение функции цели в точке А(2,5; 1,5)

f(x)_max = 2 × 2,5 + 1,5 = 6,5.