Меню
Главная
Авторизация/Регистрация
 
Главная arrow Экономика arrow Исследование операций в экономике

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

В параграфе 1.3 были рассмотрены различные формы задачи линейного программирования и показано, что любая задача линейного программирования может быть представлена в виде общей, канонической или стандартной задачи.

В данном параграфе будем рассматривать каноническую задачу (1.20)-(1.22), в которой система ограничений есть система уравнений (2.1).

Для обоснования свойств задачи линейного программирования и методов ее решения целесообразно рассмотреть еще два вида записи канонической задачи.

Матричная форма записи:

(3.6)

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

(3.7)

(3.8) где

Здесь С – матрица-строка; А – матрица системы; X – матрица-столбец переменных; В – матрица-столбец свободных членов.

Векторная форма записи:

(3.9)

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

(3.10)

(3.11)

где СХ – скалярное произведение векторов[1] и, векторы

состоят соответственно из коэффициентов при переменных и свободных членов.

Векторное неравенство X > 0 означает, что все компоненты вектора X неотрицательны, т.е. Xj >0, j = 1,2,..., η.

В гл. 2 была сформулирована, но нс доказана в общем виде следующая теорема.

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

□ Пусть и два допустимых решения задачи (3.6)-(3.8), заданной в матричной форме. Тогда АХх и ЛХ2 = В. Рассмотрим выпуклую линейную комбинацию решений X, и Х.2, т.е.

при

и покажем, что она также является допустимым решением системы (3.7). В самом деле,

т.е. решение X удовлетворяет системе (3.7). Но так как X, >0, Х2 > 0, оц >0, а2 > 0, то и X > 0, т.е. решение X удовлетворяет и условию (3.8). ■

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

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

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

□ Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через X,, Х2,..., Хр, а оптимальное решение – через X* (рис. 3.3). Тогда Е(Х*)>Е(Х) для всех точек X многогранника решений. Если X* – угловая точка, то первая часть теоремы доказана.

Предположим, что X' не является угловой точкой, тогда на основании теоремы 3.1 X* можно представить как выпуклую линейную комбинацию угловых точек многогранника решений, т.е.

Так как F(X) – линейная функция, получаем

(3.12)

В этом разложении среди значений F(X) ( / = 1,2 … р) выберем максимальное. Пусть оно соответствует угловой точке Xk {<к< р); обозначим его через М, т.е. F(Xk) = М. Заменим в выражении (3.12) каждое значение этим максимальным

Рис. 3.3

значением М. Тогда, учитывая, что, найдем . По предположению X – оптимальное решение, поэтому, с одной стороны, F(X*)> F(Xk) = М, но, с другой стороны, доказано, что F(X*)<M, следовательно, F(X')= М – F(Xk). где Хк – угловая точка. Итак, существует угловая точка Хк, в которой линейная функция принимает максимальное значение.

Для доказательства второй части теоремы допустим, что F(X) принимает максимальное значение более чем в одной угловой точке, например в точках Xv Х2, ..., X , где 1 < q < р. тогда F(X{) = F(X2) =... = F(Xq) = Μ.

Пусть X – выпуклая линейная комбинация этих угловых точек, т.е.

В этом случае, учитывая, что функция F(X) линейная, получим

т.е. линейная функция F принимает максимальное значение в произвольной точке X, являющейся выпуклой линейной комбинацией угловых точек Xv Х.2,..., Xq. ■

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

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

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

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

□ Пусть ^ = (^2,...,^(),0,...,°) – допустимое базисное решение системы ограничений (3.10) задачи, в котором первые т компонент – основные переменные, а остальные п – т компонент – неосновные переменные, равные нулю в базисном решении (если эго не так, то соответствующие переменные можно перенумеровать). Покажем, что X – угловая точка многогранника решений.

Предположим противное, т.е. что X не является угловой точкой. Тогда точку X можно представить внутренней точкой отрезка, соединяющего две различные, не совпадающие с X, точки,

другими словами, выпуклой линейной комбинацией точек Х{ и Х2 многогранника решений, т.е.

(3.13)

где а, > 0, а2 > 0 и а, + ot2 = 1 (полагаем, что а, * 0, ос2 / 0, так как в противном случае точка X совпадает с точкой Хх или Х2).

Запишем векторное равенство (3.13) в координатной форме:

Поскольку χψ > 0, χψ > 0 (j = 1,2,п), а, > 0, а9 > 0, то из последних п – т равенств следует, что = 0, = О, х^ = 0, χ12) = 0, т.е. в решениях Xv Х2 и X системы уравнений (3.10) значения п-т компонент равны в данном случае нулю. Эти компоненты можно считать значениями неосновных переменных. Но значения неосновных переменных однозначно определяют значения основных, следовательно, = т, = .т,,...,х^ = х*2) = х,„. Таким образом, все п компонент в решениях X, Хх и Х2 совпадают, и значит, точки Хх и Х2 сливаются, что противоречит допущению. Следовательно, X – угловая точка многогранника решений.

Докажем обратное утверждение. Пусть X = (хр ху ..., хт; 0, 0,..., 0) – угловая точка многогранника решений и первые ее т координат положительны. Покажем, что X – допустимое базисное решение.

Если векторы Pv Рг ..., Рт линейно независимы[3], то ранг г матрицы А, составленной из компонент этих векторов, равен т, т.е. определитель |л|*0, следовательно, переменные xv х2, ..., х являются основными и решение X = (xvx2,...,xm,0 0) – базисное, допустимое, т.е. утверждение доказано.

Предположим противное, т.е. векторы Р{, РТ ..., Рщ линейно зависимы; тогда в равенстве

(3.14)

хотя бы один из коэффициентовотличен от нуля.

Умножим почленно равенство (3.14) на множитель μ > 0:

(3.15)

Подставив координаты угловой точки X многогранника решений в систему ограничений (3.10), получим

(3.16)

Равенство (3.15) почленно сложим с равенством (3.16), а затем вычтем его из равенства (3.16). Получим

(3.17)

(3.18)

Сравнивая полученные равенства (3.17), (3.18) с равенством (3.16), заключаем, что при любом μ системе ограничений (3.10) удовлетворяют решения Xt =(^ +ра1,...,д:от + раш; O, 0,...,0) и Х2 =(л-1-ра1,...,хш-раш;0,0 0).

Поскольку Xj > 0 (J = 1,2,..., и), то можно подобрать μ настолько малым, что все компоненты решений Х] и X., будут неотрицательными. В результате X. и X., будут различными допустимыми решениями задачи (3.9)-(3.11). При этом, как легко видеть, решение, т.е. точка X лежит на отрезке (в данномслучае в его середине), расположенном в многограннике решений. Значит, X не является угловой точкой, что противоречит условию. Следовательно, наше допущение неверно, т.е. векторы Ру P, г ..., Рщ линейно независимы и X – допустимое базисное решение задачи (3.9)-(3.11). ■

Из теорем 3.3 и 3.4 непосредственно вытекает важное следствие: если задача линейного программирования имеет оптимальное решение, то оно совпадает по крайней мере с одним из ее допустимых базисных решений.

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

  • [1] Скалярным произведением СХ двух векторов и называется число, равное сумме произведений соответствующих координат этих векторов:
  • [2] Формулировка теоремы остается такой же и при отыскании минимального значения линейной функции.
  • [3] Векторы Рг ..., Рп (они же столбцы матрицы Л) называются линейно зависимыми, если можно подобрать такие числа а,, ге.,,..., ап, не равные нулю одновременно, что α,Ρ, + а.2Р.2+... + а.лР„ =0, где 0 – нулевой вектор (состоящий из нулей). В противном случае векторы 1. Р2,..., Рт называются линейно независимыми.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы