Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

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

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

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

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

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

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

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

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

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

На основе сформулированного выше утверждения точку х* можно представить в виде выпуклой комбинации угловых точек х1, х2,..., xm

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

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

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

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


  • Разделы

  • Партнеры