Основы теории линейного программирования

1. Двойственные задачи линейного программирования: графический метод решения основной задачи

1.1. Двойственные задачи линейного программирования. Линейное программирование занимается изучением экстремальных задач, в которых ищется максимум или минимум линейной функции в арифметическом конечномерном векторном пространстве на множестве векторов, удовлетворяющих конечному числу линейных уравнений и (или) неравенств.

В качестве основной в линейном программировании принята следующая задача максимизации линейной функции на множестве решений линейных уравнений и неравенств.

Задача I. заданы вещественные числа

, , , ,

и фиксированные разбиения каждого из множеств

,

на два непересекающихся подмножества

, ; , .

Требуется максимизировать линейную функцию

(1)

на множестве n-мерных векторов.

, (2)

удовлетворяющих условиям

, ; (3)

, ; (4)

, . (5)

Вектор (2), удовлетворяющий условиям (3)–(5), называется допустимым, а искомый допустимый вектор, доставляющий максимум функции (1) – оптимальным.

Наряду с задачей 1 рассматривается следующая двойственная к ней экстремальная задача.

Задача I^*. При исходных данных задачи I минимизировать линейную функцию

(6)

на множестве m-мерных векторов

, (7)

удовлетворяющих условиям

, ; (8)

, ; (9)

, . (10)

Вектор (7), удовлетворяющий условиям (8)–(10) называется допустимым, искомый допустимый вектор, доставляющий минимум функции (6) – оптимальным.

Каждому ограничению основной задачи отвечает в двойственной задаче переменная , а каждой переменной задачи I – ограничение с номером j задачи I^*. При этом переменная неотрицательная, если _. Аналогично в задаче I^* ограничения, отвечающие неотрицательным , задаются в виде неравенств. Сказанное, с учетом одинаковых исходных данных < > позволяют без излишней формализации по заданной задаче I записать двойственную ей задачу I^*.

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

μ(x)=2х₁ – х₂ + 3х₃ + х₄ – 5х₅

на множестве векторов

х=(х₁, х₂, х₃, х₄, х₅),

удовлетворяющих условиям

х₁ ≥ 0, х₂ ≥ 0, х₄ ≥ 0,

3х₁+ х₂ – 4х₃+ х₅ – 6 ≥ 0,

3х₂+4х₃ – 2х₄ +1 ≥ 0,

2х₁ + х₃ – 3х₄ – 2х₅ = 0.

В этой задаче I={1,2,3}; I₁={3}; I₂={1,2}; J={1,2,3,4,5}; J₁={3,5}; J₂ ={1,2,4}.

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

ν(y)= – 6y₁ + y₂

на множестве векторов

y=(y₁, y₂, y₃),

удовлетворяющих условиям:

у₁ ≥ 0, у₂ ≥ 0,

3у₁ + 2у₂ + 2 ≤ 0,

у₁ + 3у₂ – 1 ≤ 0,

–4у₁ + 4у₂ + у₃ + 3 = 0,

– 2у₂ – 3у₃ + 1 ≤ 0,

у₁ – 2у₃ – 5=0.

Достаточный признак оптимальности в краткой форме. Для оптимальности допустимого вектора (2) в задаче I достаточно, чтобы в задаче I^* нашелся допустимый вектор (7), удовлетворяющий условию

μ(x) = ν(y) (11)

при этом допустимый вектор (7) является оптимальным в задаче I^*.

Достаточный признак оптимальности в развернутой форме. Для оптимальности допустимого вектора (2) в задаче I достаточно существования m-мерного вектора

y = (y₁, y₂,…, y_m),

удовлетворяющего следующим условиям:

а) y_j ≥ 0, ;

б) , ;

в) , ;

г) , если x_j>0, ;

д) у_i = 0, если , .

При этом вектор y = (y₁, y₂,…, y_m) является оптимальным в задаче I^*.

Заметим, что ограничения а),б) и в) совпадают с условиями допустимости вектора (7) в задаче I^*.

1.2.Графический метод решения задачи линейного программирования. Наглядным является графический метод решения основной задачи. Воспользуемся им для предварительного решения и анализа содержательной задачи ЛП. Однако он применим, когда n≤3.

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

Таблица 1 Таблица 2

промежуточный продукт	выход из 1т сырья, кг
1	460
2	200
3	340

промежуточный продукт	расходы п. пр. на 1т конечного продукта., кг
	1	2
1	250	800
2	250	200
3	500	---

Технологический процесс состоит из двух этапов. На первом этапе поступающее сырье перерабатывается в три промежуточных продукта, которые на втором этапе используются для получения конечной продукции. Выход промежуточных продуктов из одной тонны сырья указан в таблице 1., а расход на производство одной тонны конечной продукции каждого вида – в таблице 2. При этом цена тонны конечной продукции первого вида 50 у.е., а второго – 60 у.е.

Задача состоит в определении производственной программы, при которой максимизируется цена выпускаемой продукции. Планируемые выпуски конечных продуктов обозначим через х₁ и х₂ соответственно. Требуется максимизировать величину

μ(х₁, х₂) = 50х₁ + 60х_2. (12)

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

х₁ ≥ 0, х₂ ≥ 0,

250х₁ + 800х₂ ≤ 460,

250х₁ + 200х₂ ≤ 200, (13)

500х₁+ 0х₂ ≤ 340

Таким образом, задача сводится к определению максимума линейной функции (12) на множестве двухмерных векторов, удовлетворяющих линейным неравенствам (13). В этой системе имеются лишь две переменные, что позволяет получить графическое решение задачи.

Каждой паре неотрицательных вещественных чисел х₁ и х₂ сопоставим в первом квадранте плоскости х₁ 0 х₂ точку М(х₁, х₂). Точки (х₁, х₂), удовлетворяющие условиям (13), заполнят пятиугольник 0АВСД (рис. 1), ограниченный осями координат и прямыми

250х₁ + 800х₂ = 460,

250х₁ + 200х₂ = 200,

500х₁ + 0 х₂ = 340.

Величина (12) пропорциональна расстоянию точки М(х₁, х₂) от прямой ОЕ, задаваемой уравнением 50х₁+60х₂=0. поэтому оптимальной программе отвечает точка пятиугольника, наиболее удаленная от прямой ОЕ.

Рис. 1. Иллюстрация графического решения примера 1

Таковой в рассматриваемом случае является точка В, в которой пересекаются прямые

250х₁ + 800х₂ = 460,

250х₁ + 200х₂ = 200.

Решая систему уравнений, находим искомую оптимальную производственную программу х⁰=(0.453;0.433), при которой суммарная цена выпускаемой продукции в расчете на одну тонну сырья составляет

μ=50*0.453+60*0.433 у.е.

Используя теперь двойственную задачу и признак оптимальности в развернутой форме, убедимся в правильности полученного решения. Запишем рассматриваемую задачу в приведенной ранее стандартной форме.

Задача I. максимизировать.

μ(х₁, х₂)= 50х₁ + 60х₂

на множестве векторов

х=(х₁, х₂),

удовлетворяющих условиям:

х₁ ≥ 0, х₂ ≥ 0,

–250х₁ – 800х₂ + 460 ≥ 0,

–250х₁ – 200х₂ + 200 ≥ 0, (14)

–500х₁ + 340 ≥ 0.

Это случай, когда I={1,2}, I₁= Ø , I₂ =I; J={1,2,3}, J₁=Ø, J₂=J, называется симметричной канонической формой. Двойственной к ней является следующая

Задача I^*. Минимизировать

ν(у)=460у₁ + 200у₂ + 340у₃

на множестве векторов

у=(у₁, у₂, у₃), у₁ ≥ 0, у₂ ≥ 0_, у₃ ≥ 0,

удовлетворяющих условиям:

а) –250у₁ – 250у₂ – 500у₃ + 50 ≤ 0,

(15)

– 800у₁ – 200у₂ + 60 ≤ 0.

Проверим выполнение оптимальности для полученного графически вектора х⁰=(0,453;0,433). Прежде всего, отметим, что этот вектор допустимый и его координаты положительные, поэтому неравенства (15), должны выполняться как равенства, т.е. имеем

б) – 250у₁ – 250у₂ – 500у₃ + 50 ≤ 0, (16)

– 800у₁ – 200у₂ + 60 = 0.

Для исследуемого вектора х⁰ первые два неравенства системы (14) выполняются как равенства, а третье ограничение – как строгое неравенство, следовательно имеем

в) у₃=0. (17)

Таким образом, для оптимальности допустимого вектора х⁰=(0.453; 0.433) достаточно существования вектора у⁰=(у₁, у₂, у₃) с неотрицательными компонентами, удовлетворяющего условиям (15), (16) и (17). Решая систему уравнений (16), (17). находим вектор у⁰=(0.033; 0.165;0) с неотрицательными компонентами удовлетворяющими (15). Таким образом, все условия (а), (б) и (в) для вектора у⁰ выполнены.

Следовательно, найденный графически вектор х⁰ является оптимальным в задаче I, а вектор у⁰ – оптимальный в задаче I^*. При этом

μ(x⁰) = ν(y⁰)=48.63.

Выясним экономический смысл для рассмотренного примера планирования производственной программы. Каждому ограничению (14), несущему смысл расхода промежуточного продукта, сопоставим оценку у_i единицы этого продукта. Тогда в задаче I^* требуется минимизировать суммарную оценку промежуточных продуктов на множестве векторов у=(у₁, у₂, у₃), неотрицательные компоненты которых имеют смысл оценки соответствующего промежуточного продукта при условии запрета на существование «сверх рентабельного» конечного продукта. А именно толкование условий (а) означает: оценка затраченных промежуточных продуктов на «производство единицы конечного продукта не может быть менее его цены». Вместе с тем условия (б) означают «производство только «рентабельных» конечных продуктов», а условий (в) «равенство нулю оценки избыточного промежуточного продукта».