шпаргалка

СВОЙСТВА РЕШЕНИЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

[ Назад ]

Для обоснования свойств задачи линейного программирования и методов ее решения приведем матричную форму записи канонической задачи:

(10.15)

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

АХ = В, (10.16)

Х ? 0, (10.17)

где

, ,

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

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

Пусть и – два допустимых плана задачи (10.15)-(10.17). Тогда , и , .

Рассмотрим выпуклую линейную комбинацию , , и покажем, что Х также является планом задачи. Действительно,

,

т.е. Х удовлетворяет (10.16). Но так как , , , , то и , т.е. удовлетворяет и условию (10.17).

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

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

Доказательство. Предположим, что многогранник решений является ограниченным, имеющим конечное число угловых точек. Обозначим его через К. В К имеет вид многоугольника, изображенного на рисунке. Обозначим угловые точки К через , , … , , а оптимальный план через . Тогда для всех Х из К. Если - угловая точка, то первая часть теоремы доказана.













Рисунок 10.2.

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

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

(10.18)

В этом разложении среди значений выберем минимальное. Пусть оно соответствует угловой точке и обозначим его через М, т.е. . Заменим в (10.18) каждое значение этим минимальным значением. Тогда, учитывая, что , , получим

.

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

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

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

, ,

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



,

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

Теорема 10.3. Если система векторов в разложении (10.14) линейно независима и такова, что



где все , то точка является угловой точкой многогранника решений.

Теорема 10.4. Если – угловая точка многогранника решений, то векторы , соответствующие положительным в разложении (10.14), линейно независимы.

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

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассмотрим задачу линейного программирования, заданную в стандартной форме. Найти

(10.19)

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

(10.20)

(10.21)

Рассмотрим случай n =2 (n = 3). Напомним, что неравенству соответствует полуплоскость с граничной прямой , координаты каждой точки которой удовлетворяют этому неравенству.

Пусть дана система m ограничений с двумя переменными, т. е.

(10.22)

(10.23)

Если множество значений , удовлетворяющих условиям (10.22) и (10.23), ограничено, то оно представляет собой выпуклый многоугольник (при n = 3 – выпуклый многогранник). Линейная форма достигает экстремума в вершине многоугольника. Если максимум (или минимум) достигается одновременно в двух вершинах, то он достигается на всей стороне многоугольника, соединяющей эти вершины, причем стороны многоугольника – это отрезки прямых, уравнения которых могут быть получены, если в (10.22) и (10.23) заменить неравенства на уравнения. Область изменения линейной формы представляет собой многоугольник, изображенный на рис. 10.3.





















Рисунок 10.3

Прямые, образующие многоугольник ОАВСЕF на плоскости соответствуют условиям (10.22) и (10.23), в которых неравенства заменены уравнениями. Штриховка указывает на ту сторону прямой, по которую располагаются точки плоскости, удовлетворяющие неравенствам (10.22) и (10.23). Направление прямой определяется вектором ; это вектор перпендикулярен . Коэффициенты и указывает также направление, в котором увеличивается линейная форма

( ).

Задача линейного программирования – вычисление координат точки, дающей экстремум линейной форме

(10.19’)

при условиях (10.22) и (10.23), может быть (при n = 2), геометрически истолкована следующим образом.

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

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

1. Графически могут решаться:

– задачи, заданные в стандартной форме, содержащие не более двух переменных;

– задачи, заданные в канонической форме с числом свободных переменных (r – ранг матрицы системы ограничений);

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

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

3. Решение задачи первого типа выполняется в два этапа: построение области допустимых решений и нахождение в этой области оптимального решения.

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

I – пустая область;

II – выпуклый многоугольник;

III – неограниченная выпуклая многоугольная область.

В случае I задача не имеет решения; в случае II задача всегда имеет оптимальное решение; в случае III, в зависимости от направления вектора (коэффициентов линейной формы F), задача может иметь или не иметь решения. Последнее связано с неограниченным возрастанием ( ) или убыванием ( ) функции в области допустимых решений.

5. Задача может иметь единственное оптимальное решение, совпадающее с одной из вершин области, и бесчисленное множество решений (альтернативный оптимум).

6. В случае альтернативного оптимума и ограниченной области оптимальные решения соответствуют всем точкам отрезка, соединяющего две вершины области (рис. 10.4). В случае неограниченной области может оказаться, что среди множества оптимальных решений только одно совпадает с вершиной области (т. на рис. 10.5). Тогда на «оптимальной» граничной прямой находят еще одно оптимальное решение и общее оптимальное решение , .















, ,

. .

Рисунок 10.4 Рисунок 10.5









КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |