Свойства решений ЗЛП

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

Теорема 9.7. Если ЗЛП имеет решение, то оно достигается в угловой точке множества планов.

Д о к а з а т е л ь с т в о. Пусть - оптимальный опорный план, т.е. для любого . Предположим противное: не является угловой точкой, тогда по теореме о представлении множества планов ЗЛП, эту точку можно представить в виде

,

где - все угловые точки множества .

Подсчитаем значение линейной формы ЗЛП в точке

.

Так как число угловых точек - конечно, то можно найти ту угловую точку , значение линейной формы в которой наибольшее

.

Тогда

.

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

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

Д о к а з а т е л ь с т в о. Пусть угловые точки таковы, что

.

Построим некоторую точку как выпуклую линейную комбинацию этих угловых точек:

.

Найдем значение линейной формы в этой точке

,

следовательно, эта точка также является решением ЗЛП.

Контрольные вопросы

1. Приведите постановку общей задачи линейного программирования.

2. Какая задача линейного программирования называется канонической?

3. Пояснить понятия плана ЗЛП и оптимального плана ЗЛП.

4. Опишите способ приведения к канонической форме задачи линейного программирования.

5. Что такое множество планов ЗЛП, какими свойствами оно обладает?

6. Поясните понятие угловой точки множества планов задачи линейного программирования.

7. Приведите необходимое и достаточное условие того, что точка является угловой точкой множества допустимых планов ЗЛП?

8. Дайте определения опорного плана и базиса опорного плана.

9. Какой опорный план называется вырожденным (невырожденным)?

10. Приведите формулировку теоремы о представлении ограниченного множества планов ЗЛП.

11. Приведите формулировку теоремы о представлении неограниченного многогранного множества планов ЗЛП

12. Перечислите свойства решений ЗЛП.