|
Читайте также: |
Определение. Линейная комбинация
точек 
называется выпуклой, если
> 0, 
> 0,…, 
> 0 и + + …+ = 1.
Определение. Множество точек называется выпуклым, если оно содержит любую выпуклую линейную комбинацию любых своих точек.
Теорема 9.1. Множество всех планов задачи ЛП является выпуклым множеством.
Доказательство. Пусть – произвольные планы задачи ЛП. Это значит, что выполняются равенства:
…, 
Пусть 
– выпуклая линейная комбинация взятых планов. Подставим в уравнение 
выражение . Используя известные нам свойства линейных операций над матрицами, получаем:
.
Таким образом, 
является планом задачи ЛП. Теорема доказана.
Определение. Точка области называется вершиной (угловой точкой), если она не является выпуклой линейной комбинацией других точек.
Это определение не опирается на наглядность, но и не противоречит обыденному нашему представлению о вершине прямоугольника, треугольника, куба и т.п.
Теорема 9.2. Если оптимальный план задачи ЛП существует, то, по крайней мере, одна из вершин является оптимальным планом.
Доказательство. Обозначим через 
оптимальный план. Будем считать, что – не вершина. Для конкретности рассуждений будем считать, что 
– наибольшее значение целевой функции. Представим в виде выпуклой линейной комбинации вершин 
, т.е.
,
где
> 0, > 0,…, > 0 и + + …+ = 1.
Тогда
М = 
) 
Дата добавления: 2015-07-26; просмотров: 127 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Решение. | | | с использованием симплекс-таблиц |