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

Доказательство. Пусть Х1=(х1(1), х2(1),…,xn(1)) и X2=(x1(2), x2(2),…,xn(2) – два допустимых решения задачи, заданной в матричной форме. Тогда АХ1=В и АХ2=В. Рассмотрим выпуклую линейную комбинацию решений Х1 и Х2, т.е. Х=α1Х1 + α2Х2 при α1≥0, α2≥0 и α1 + α2 =1, и покажем, что она также является решением системы. В самом деле, АХ = А(α1Х1 + α2Х2) = α1АХ1 + (1- α1)АХ2 = α1В + (1- α1)В=В, т.е. решение Х удовлетворяет системе. Но так как Х1≥0, Х1≥0, α1≥0, α2≥0, то и Х ≥0, т.е решение Х удовлетворяет и условию.

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

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

Доказательство. Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х1, Х2, …, Хр, а оптимальное решение – через Х*. Тогда F(X*)≥F(X) для всех точек Х многогранника решений. Если Х* - угловая точка, то первая часть теоремы доказана. Предположим, что Х* не является угловой точкой , тогда на основании теоремы о выпуклом многоугольнике, являющемся выпуклой линейной комбинацией своих угловых точек, Х* можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е. Х*= α1Х1 + α2Х2 +…+ αрХр, αj≥0, j=1,p; j=1Σn αj=1.

Так как F(X) линейная функция, получаем F(X*)=F(α1Х1 + α2Х2 +…+ αрХр)= α1F(X1) + α2F(X2) + … + αpF(Xp). (1)

В этом разложении среди значений F(xj) (j=1,p) выберем максимальное. Пусть оно соответствует угловой точке Xk (1≤k≤p); обозначим его черех М, т.е. F(Xk)=M. Заменим в выражении (1) каждое значение этим максимальным значением М. Тогда, учитывая, что αj≥0, j=1Σp αj=1, найдем F(X*)≤α1M + α2M + … + αpM= M j=1 Σp αj=M. По предположению Х* - оптимальное решение, поэтому, с одной стороны, F(X*)≥F(Xk)=М, но, с другой стороны, доказано, что F(X*)≤М, следовательно, F(X*)=М=F(Xk), где Xk – угловая точка. Итак, существует угловая точка Xk, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(X) принимает максимальное значение более чем в одной угловой точке, например, в точках X1, X2, … Xq, где 1≤q≤p; тогда F(X1)=F(X2)=…=F(Xq)=M.

Пусть Х – выпуклая комбинация этих угловых точек, т.е Х= α1Х1 + α2Х2 +…+ αqХq, aj≥0 (j=1,q), j=1Σq aj=1. В этом случае, учитывая, что функция F(X) – линейная, получим F(X)=А(α1Х1 + α2Х2 +…+ αqХq)= α1F(X1) + α2F(X2) + … + αqF(Xq) = α1M + α2M +…+ αqM = M j=1Σq aj=M, т.е. линейная функция F принимает максимальное значение в произвольной точке Х, являющейся выпуклой линейной комбинацией угловых точек X1, X2,…., Xq.

Нахождение исходного опорного решения.

1) Фиксируют уравнение с максимальным по модулю отрицательным свободным членом.

2) Почленно вычитают фиксированное уравнение из остальных уравнений с отрицательными свободными членами.

3) Обе части фиксированного уравнения умножают на «-1».

4) Остальные уравнения системы с неотрицательными свободными членами переписывают без изменений.

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

а) Все коэффициенты при неизвестных в фиксированном уравнении неположительны, т.е. опорных решений нет.

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

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

Симплексный метод.

Симплексный метод позволяет путем ряда преобразований, состоящих в переходе от одного опорного решения к другому (причем так, что значение целевой функции все время возрастает (max) или убывает (min)), находить оптимальное решение за конечное число шагов, либо показать неразрешимость исходной задачи.

Подготовкак решению задачи симплексным методом:

1) приведение задачи к каноническому виду

2) приведение системы уравнений к единичному базису

3) нахождение исходного опорного решения

Решение симлекс-методом:

1. Найти опорный план.

2. Составить симплекс-таблицу.

3. Исходный опорный план проверить на оптимальность, в результате чего может иметь место один из 3 случаев:

а) если Δj≥0, то исходный опорный план является оптимальным.

б) если Δj<0 и все элементы соответствующего столбца ≤0, то целевая функция не огранична сверху на множестве ее плана.

в) Δj<0 и для каждого такого j по крайней мере одно aij положительное, то можно перейти от исходного опорного плана к новому опорному плану, при котором значение целевой функции возрастает.

4. Найти разрешающий столбец и разрешающую строку. Разрешающий столбец определяется наибольшей по абсолютной величине отрицательной оценкой Δj. Разрешающая строка определяется минимальным отношением свободных членов к положительным элементам разрешающего столбца.

5. Сделать соответствующие замены в столбцах Вб и Сб и проделать один шаг метода Ж. Гауса с найденный разрешающим элементом. Пересчитать элементы в строке Δ.

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

Приращение целевой функции

Приращение – разность между последующей и предыдущей функциями

∆ = Z2 – Z1 >0

X1 àZ(X1) =Z1

|       |      |  

X2 àZ(X2) =Z2

Z2=(z1aij-∆jbi) \ aij=Z1 - ∆jbi\aij

∆ = Z1 - ∆jbi/ aij – Z1 = -∆jbi/ aij > 0

∆j < 0

Критерии оптимальности

Теорема 1: Опорный план Х*=(х1*, х2*, 0,…, 0) задачи (1) – (3) является оптимальным, если ∆j ≥0, j = 1, n.

Теорема 2: Если ∆k< 0 для некоторого j=k и среди чисел aik нет положительных (aik ≤ 0), то целевая функция (1) задачи (1) – (3) не ограничена на множестве ее планов.

Теорема 3: Если ∆k < 0 и опорный план Х задачи (1) – (3) не вырожден, но среди чисел aik есть положительные (не все aik ≤ 0), то существует опорный план Х’ такой что Z(X’) >Z(X)

Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

Метод невязок.

Часто при решении задачи линейного программирования используется искусственный базис. Метод решения при помощи искусственного базиса называется методом невязок. Рассмотрим в качестве примера задачу линейного программирования с пятью неизвестными:

Z = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 (max) (1)

a1x1 + a2x2 + a3x3 + a4x4 + a5x5 = a        

b1x1 + b2x2 + b3x3 + b4x4 + b5x5 = b          (2)

c1x1 + c2x2 + c3x3 + c4x4 + c5x5 = c

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0      (3)

a ≥ 0, b ≥ 0, c ≥ 0                                  (4)

Если одно или несколько условий (4) не выполняются, например a < 0, то, умножив обе части первого равенства на -1, получим уравнение, в котором свободный член больше. нуля.

Наряду с исходной задачей (1) – (4) рассмотрим другую задачу линейного программирования, которая является вспомогательной:

Т = c1x1 + c2x2 + c3x3 + c4x4 + c5x5 + М (V1 + V2 + V3) (max)

при условиях

a1x1 + a2x2 + a3x3 + a4x4 + a5x5 + V1 = a        

b1x1 + b2x2 + b3x3 + b4x4 + b5x5 + V2 = b        

c1x1 + c2x2 + c3x3 + c4x4 + c5x5 + V3 = c

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, V1 ≥ 0, V2 ≥ 0, V3 ≥ 0

где М – некоторое число.

Эта задача называется М-задачей. Неизвестными в ней являются x1, x2, x3, x4, x5, V1, V2, V3. При этом неизвестные V1, V2, V3 называются искусственными.

При решении задачи линейного программирования используется следующая теорема:

1. Если в оптимальном решении М-задачи все искусственные переменные равны нулю, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи.

2. Если имеется оптимальное решение М-задачи, в котором одна из искусственных переменных отлична от нуля, то система ограничений (исходная задача не имеет допустимого решения).

3. Если М-задача не имеет оптимального решения, то исходная задача не разрешима.

Двойственные задачи.

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

· число переменных двойственной задачи равно числу условий ограничений прямой задачи (не считая условий неотрицательности переменных) и наоборот число условий ограничений двойственной задачи равно числу переменных исходной задачи;

· коэффициентами целевой функции двойственной задачи служат свободные члены системы ограничений прямой задачи, а свободными членами системы ограничений двойственной задачи – коэффициенты целевой функции исходной задачи;

· матрицей коэффициентов при переменных двойственной задачи будет транспонированная матрица из коэффициентов при переменных системы ограничений исходной задачи;

· если исходная задача решается на max и ее неравенства приведены к виду ≤ то двойственная к ней задача решается на min и ее неравенства в системе ограничений должны быть вида ≥ (целевая установка);

· каждому i-ому ограничению-неравенству прямой задачи соответствует в двойственной задачи условие неотрицательности i-ой переменной (yi ≥ 0), а ограничению-равенству соответствует переменная без ограничений. И наоборот, неотрицательной переменной прямой задачи соответствует в двойственной задачи k-ое ограничение-неравенство, а произвольной переменной – ограничение-равенство.

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

Исходная и двойственная к ней задачи могут быть экономически интерпретированыследующим образом:

Исх. задача: составить план выпуска продукции, обеспечить ее max выпуск в стоимостном выражении.

Двойственная: какова должна быть цена единицы каждого из ресурсов для минимизации общей стоимости затрат.

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

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

Лемма 1. Если Х – некоторый план исходной задачи (43) – (45), a Y – произвольный план двойственной задачи (46), (47), то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т. е. F(x)≤F*(Y) или j=1Σn CjXj ≤ i=1Σm biyi.

Лемма 2. Если для некоторых планов X* и Y* задач (43) – (45) и (46), (47), то X* – оптимальный план исходной задачи, а Y* – оптимальный план двойственной задачи.

22-23. Симметричные и несимметричные двойственные задачи. Нахождение оптимального решения. Пример.

Пары двойственных задач делятся на симметричные и несимметричные. Если в системе ограничений нет ограничений вида равенства и в обеих задачах нет произвольных переменных, то такая пара задач называется симметричной. В противном случае задачи несимметричны.

Решение двойственных задач:

Z = c₁x₁ + c₂x₂ + … + c_nx_n (max)

       x₁x₁ + … + a_nx_n £ b₁

                 …

       a_nx₁ + … + a_mnx_n £ b_m

"x_j ³ 0; j=1,n