Математические методы исследования операций в экономике (стр. 5 из 37)

На рис. 1.1 изображен некоторый частный случай, для которого решение ЗЛП достигается в угловой точке х* = (0, 6) области D. Нетрудно представить, что возможны и другие варианты. Они изображены на рис. 1.2.

Рисунок (а) иллюстрирует ситуацию неограниченности целевой функцииf(x)=cx на множестве D, т.е. сколько бы мы ни перемещались по линиям уровня в направлении вектора с, ее значение будет возрастать.

В случае, изображенном на рисунке (b), линия уровня, соответствующая максимальному значениюf(x), касается грани множестваD, и, соответственно, все точки, лежащие на этой грани, являются оптимальными планами.

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

Заметим также, что аналогичным образом могут быть построены интерпретации ЗЛП для случая трехмерного пространстваR³, где множеству D будет соответствовать некоторый ограниченный или неограниченный многогранник, а поведение целевой функции будет характеризоваться поверхностями (плоскостями) уровня.

Несмотря на свою очевидную ограниченность, графический метод решения ЗЛП часто оказывается полезным. В частности, он может быть применен не только к задачам с двумя переменными и ограничениями в виде неравенств, но и к каноническим задачам вида (1.7), у которых n - m = 2, где n — количество переменных, а m — ранг матрицы А.

Действительно, можно выбрать две произвольные переменные х_j1,x_j2 и, используя систему уравнений, выразить через них остальные переменные

где φ_j(x_j1, x_j2) —линейные функции.

Подставив выражения (1.9) в целевую функцию, мы получим эквивалентную задачу

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

Последняя ЗЛП может быть решена графически.

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

Теорема 1.1. Если целевая функция f принимает максимальное значение в некоторой точке множества допустимых планов D, то она принимает это значение и в некоторой угловой точке данного множества.

Доказательство.

Чтобы не усложнять изложение, ограничимся тем случаем, когда множество D ограничено, и, следовательно, является выпуклым многогранником.

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

Если D — замкнутое ограниченное выпуклое множество, имеющее конечное число угловых точек, то любая точка х Î D может быть представлена в виде выпуклой комбинации угловых точек D*.

* Строгое доказательство данного утверждения см., например, в [14].

Пусть х¹, х²,…,х^m— угловые точки множестваD, а х* — точка, в которой целевая функция fдостигает максимума.

На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых точек х¹, х²,..., x^m

Так как х* — точка максимума, то для любого х Î D сх* ≥ сх. Функцияf(x) — линейная, поэтому

cледовательно,

где x^r— угловая точка, удовлетворяющая условию

Из (1.10) видно, что сх* ≤сх^r.В то же время справедливо обратное неравенство: сх* ≥ сх^r. Откуда следует, что сх* = сх^r, т. е. существует по крайней мере одна угловая точках^r, в которой целевая функция принимает максимальное значение. -

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

Доказательство.

Пусть максимальное значение функции f достигается в точках х̃¹, х̃²,...,x̃^s , т. е. сх^~i=f*,iÎl:s. Рассмотрим произвольную выпуклую комбинацию этих точек

Найдем значение целевой функции в точке х*

Итак, для произвольной выпуклой комбинации х* точек х̃¹, х̃²,...,x^~s справедливо равенство

1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП

1.3.1. Векторная форма записи КЗЛП и ее применение. Рассмотрим каноническую задачу линейного программирования

Обозначим через а^j столбцы матрицы А и будем рассматривать их как векторы пространстваR^m. Тогда каждому допустимому плану КЗЛП — n-мерному вектору х — соответствует неотрицательная линейная комбинация столбцов а^j, равная столбцуbÎ R^m:

Такое представление ограничений КЗЛП обычно называют векторной формой записи.

Векторы а^j, j Î l:nбудем называть векторами требований задачи (D, f), а вектор b — вектором ограничений. Множество всех неотрицательных линейных комбинаций столбцов а^j с геометрической точки зрения может быть представлено как многогранный выпуклый конус, натянутый на систему векторов а^j в пространстве R^m (рис. 1.3).

Соответственно, вопрос о существовании допустимого плана задачи (D, f) равнозначен вопросу о принадлежности вектора b данному конусу, а компоненты х_j некоторого допустимогоплана хÎDявляются не чем иным, как коэффициентами разложения вектора ограничений задачи b по векторам, требований а^j.

Такое представление КЗЛП получило название второй геометрической интерпретации.

В дальнейшем без ограничения общности можем предполагать, что число уравнений, задающих множествоD, меньше или равно числу переменных задачи (m ≤ n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, значит, множество D пустое), либо содержит избыточные (линейно зависимые) уравнения.

Если некоторые т столбцов а^j1 ,а^j2 ,...,а^jmматрицы A являются линейно независимыми, то они образуют базис в пространстве R^m, и их, вообще говоря, будет достаточно для представления вектора b в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицательными, то мы получаем так называемый базисный допустимый план х, у которого не более m компонентов отличны от нуля. Сформулируем определение базисного плана более строго, так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.

-Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и β= {а^j1, аj2,..., а^jm} —линейно независимая система столбцов матрицы А, образующая базис R^m. Обозначим множество номеров столбцов, входящих в систему b, через N(β) = {j₁, j₂,..., j_m}. План х называется базисным планом задачи (D,f),если его компоненты, соответствующие базисным столбцам и называемые базисными компонентами, больше или равны нулю (х_j≥0, j Î N(β)}, а все остальные компоненты (небазисные) — равны нулю(x_j = 0, j Ï N (β)).