Теоремы о представлении множества планов злп
Теорема 9.5 (теорема о представлении множества планов ЗЛП). Пусть множество планов ЗЛП - выпуклое замкнутое ограниченное множество, - совокупность всех угловых точек . В таком случае множество является выпуклой оболочкой множества , т.е.
Эта теорема позволяет представить все многообразие точек многогранника через конечное число его угловых точек. Коэффициенты определяются однозначно только в том случае, если множество имеет ровно угловых точек. Такой многогранник называется симплексом.
Пример 9.3. Симплекс в пространстве . Убедимся, что определяются однозначно для любого из (рис. 9.1).
Рис 9.1. Множество .
Любую внутреннюю точку отрезка можно представить как , . Введем следующие обозначения
,
Таким образом, существуют :, , , .
Пример 9.4. Симплекс в пространстве . Убедимся, что определяются однозначно для любого из (рис 9.4).
Рис 9.4. Множество .
Для симплекса в выше показана однозначность представления. Значит
-
для имеем , , , ;
-
для имеем , , , .
Объединяя, получим
.
Если обозначить , , , то
,
причем
,
т.е. однозначно нашли коэффициенты такие, что
,
для любого из .
Теорема 9.6 (теорема о представлении неограниченного многогранного множества планов ЗЛП). Пусть множество планов ЗЛП - выпуклое неограниченное замкнутое множество. Точки - все угловые точки множества , - направляющие вектора его неограниченных ребер. Тогда множество совпадает с совокупностью точек вида
Свойства решений злп
Задача линейного программирования может не иметь решения, если либо целевая функция F неограниченна на множестве допустимых планов M, либо система ограничений задачи несовместна.
Теорема 9.7. Если ЗЛП имеет решение, то оно достигается в угловой точке множества планов.
Д о к а з а т е л ь с т в о. Пусть - оптимальный опорный план, т.е. для любого . Предположим противное: не является угловой точкой, тогда по теореме о представлении множества планов ЗЛП, эту точку можно представить в виде
,
где - все угловые точки множества .
Подсчитаем значение линейной формы ЗЛП в точке
.
Так как число угловых точек - конечно, то можно найти ту угловую точку , значение линейной формы в которой наибольшее
.
Тогда
.
Следовательно, нашлась точка такая, что . Но так как для любого мы пришли к противоречию, а значит - угловая точка множества планов ЗЛП.
Теорема 9.8. Если линейная форма ЗЛП достигает наибольшего значения более чем в одной угловой точке, то она достигает максимальное значение и в любой точке, являющейся выпуклой линейной комбинацией данных угловых точек.
Д о к а з а т е л ь с т в о. Пусть угловые точки таковы, что
.
Построим некоторую точку как выпуклую линейную комбинацию этих угловых точек:
.
Найдем значение линейной формы в этой точке
,
следовательно, эта точка также является решением ЗЛП.
Контрольные вопросы
1. Приведите постановку общей задачи линейного программирования.
2. Какая задача линейного программирования называется канонической?
3. Пояснить понятия плана ЗЛП и оптимального плана ЗЛП.
4. Опишите способ приведения к канонической форме задачи линейного программирования.
5. Что такое множество планов ЗЛП, какими свойствами оно обладает?
6. Поясните понятие угловой точки множества планов задачи линейного программирования.
7. Приведите необходимое и достаточное условие того, что точка является угловой точкой множества допустимых планов ЗЛП?
8. Дайте определения опорного плана и базиса опорного плана.
9. Какой опорный план называется вырожденным (невырожденным)?
10. Приведите формулировку теоремы о представлении ограниченного множества планов ЗЛП.
11. Приведите формулировку теоремы о представлении неограниченного многогранного множества планов ЗЛП
12. Перечислите свойства решений ЗЛП.