Образовательная программа: Вычислительная техника и программное обеспечение 8D06104
жүктеу/скачать 221,11 Kb.
|
Лекция 6. Математическая модель ЛП. Часть 1
- Бұл бет үшін навигация:
- Определение 2.
- Определение 4.
- Определение 6.
| Определение 1. План Х = (х1, х2, …, хn) называется опорным планом основной задачи ЛП, если система векторов Pj с полисистемными коэффициентами хj – линейно независима.
Определение 2. Опорный план называется невырожденным, если он содержит ровно m – положительных компонентов, в противном случае – он называется вырожденным. Определение 3. Пусть х1, х2, …, хn – произвольные точки евклидова пространства En. Выпуклой линейной комбинацией этих точек называется сумма α1 х1 + α2 х2 + … + αn xn, где αi – произвольное неограниченное число, такое что Определение 4. Множество называется выпуклым, если вместе с любыми двумя своими числами оно содержит их произвольную линейную комбинацию. Определение 5. Точка Х выпуклого множества называется угловой, если она не может быть представлена в виде выпуклой линейной комбинации каких-нибудь двух различных чисел. Теорема 1. Множество планов основной задачи ЛП является выпуклым. Определение 6. Непустое множество планов основной задачи ЛП называется многогранником решений, а всякие условия точки многогранника – вершиной. Теорема 2. Если основная задача ЛП имеет оптимальный план, то максимальное решение функции задачи принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся линейной комбинацией этих вершин. Сформулированные теоремы позволяют сделать выводы: 1. непустое множество планов основных задач ЛП образуют выпуклый многогранник; 2. каждая вершина этого многогранника определяет опорный план; 3. в одной из вершин многогранника решений значение целевой функции максимально; 4. если максимальное значение функция принимает более, чем в одной точке, то она принимает максимальное значение в любой другой точке являющихся выпуклой линейной комбинацией данных вершин. жүктеу/скачать 221,11 Kb. Достарыңызбен бөлісу:
|