![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Множество планов ЗЛП и его свойства
Определение 9.2. Множество векторов X, удовлетворяющих ограничениям задачи составляет множество допустимых планов данной задачи M= Тогда каноническую ЗЛП в матричной форме можно переписать следующим образом: Решить данную ЗЛП, значит найти оптимальный план задачи, т.е. такой план задачи, значение линейной формы в котором максимально: Теорема 9.1. Множество Д о к а з а т е л ь с т в о. Множество называется выпуклым, если любые две его точки входят в него вместе с отрезком их соединяющим. Таким образом, чтобы доказать выпуклость М, надо доказать, то что для любых Пусть Выберем некоторый параметр т.е. точка Теорема 9.2. Множество Д о к а з а т е л ь с т в о. Замкнутым называется множество, содержащее все свои граничные точки. Точка называется граничной точкой множества, если в любой окрестности этой точки есть как точки множества, так и точки ему не принадлежащие. Если
а сама точка являются предельными. Пусть Х- произвольная предельная точка множества М и пусть последовательность То есть, все предельные точки Теорема 9.3. Множество Д о к а з а т е л ь с т в о. Гиперплоскостью в Следовательно, множество планов ЗЛП, являющееся множеством точек Определение 9.3. Точка Теорема 9.4. Чтобы точка Д о к а з а т е л ь с т в о. Необходимость. Пусть Предположим противное: система векторов
С другой стороны, так как
Умножим обе части равенства (9.8) на произвольное положительноечисло
Очевидно, Это означает, что Достаточность. Пусть вектора
Из этого равенства, с учетом условий Далее в силу принадлежности точек
Вычитая из одного равенства другое, получим
Точки Следствие 1. Любая угловая точка Следствие 2. Для любой угловой точки множества планов ЗЛП количество линейно независимых векторов, соответствующих положительным координатам, не может быть больше ранга матрицы условий. Пользуясь данными утверждениями об угловых точках можно: · проверить, является ли некоторая заданная точка угловой или нет; · построить угловую точку данного множества. Для ответа на первый вопрос нужно проверить являются ли вектора условий, соответствующие положительным координатам данной точки, линейно независимыми. Построить угловую точку заданного множества планов можно по следующему алгоритму: 1. Вычислить ранг 2. Всем координатам, номера которых не совпадают с номерами выделенных векторов условий присвоить нулевое значение, т.е. 3. Тогда оставшиеся Число столбцов в матрице Определение 9.4. План ЗЛП, соответствующий угловой точке множества планов называется опорным планом. Определение 9.5. Базисом опорного плана называется любая система из r (где Определение 9.6. Опорный план называется невырожденным, если число положительных компонент равно рангу матрицы условий. Опорный план называется вырожденным, если число положительных координат меньше ранга матрицы условий. Невырожденный опорный план имеет единственный базис, а вырожденный опорный план может иметь несколько базисов, т.к. столбцы, соответствующие положительным компонентам, а их меньше r, могут быть дополнены до системы из r линейно независимых столбцов присоединением различных столбцов. Все небазисные компоненты любого опорного плана (вырожденного или невырожденного) равны нулю. Все базисные компоненты невырожденного опорного плана строго больше нуля. Пример 9.2. Пусть множество допустимых планов M задано системой уравнений: Найдем угловую точку данного множества. Выпишем матрицу условий Нетрудно заметить, что столбцы Таким образом, мы нашли угловую точку Проверим, является ли вектор Подставим координаты точки в исходную систему ограничений: Таким образом, координаты Легко проверить, что ранг матрицы Рассмотрим систему из трех векторов Система векторов
Дата добавления: 2014-01-06; Просмотров: 2476; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |