Поиск угловых точек

Каноническая задача линейного программирования

Для удобства поиска угловых точек в задачу линейного программирования следует приводить к каноническому виду (КЗЛП).

КЗЛП – _jx_j

Это задача на максимум 1, для не отрицательных переменных это 3-ка, в этой задаче n-переменных и m-равенств.

Любую ЗЛП можно привести к эквивалентвоной КЗЛП (решения которых одинаковые)

Переход к КЗЛП

1. Переход от минимума к максимуму

Min L=3X1+5X2-6X3

Max L^*=-3X1-5X2+6X3

L=L^*

2. Переход от неравенства к равенству.

3X1-4X2+5X3 <=10

Дополнительные неотрицательные переменные X’ и X** называются слековыми (X*) переменными и сурклассовые (X**) переменные. Они имеют простой экономический смысл, пусть ограничение по ресурсам 10 – это запасы ресурсов, тогда Х* слековое, остаток от запаса ресурса 10. Если затраты этих ресурсов 3X1-4X2+5X3/.

Если ресурс расходуется полностью то сллековое X’ расходуется полностью, в угловых точках одна или все слековые переменные могут быть нулевые. Если 3 это минимальный уровень для какого-то параметра, то сурплассовые переменные Х”, это превосходство параметра 7Х1+5Х2+6Х3 над тройкой.

В угловой точке сурплассовые переменные так же может быть нулевой.

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

X <=> 0 От такой переменной легко перейти к неотрицательной переменной. Если вспомнить 4-ый класс школы))) x=x’-x”, x’,x”=>0 Любое число можно представить в виде разности двух неотрицательных чисел и подставить это в ЗЛП.

Пример приведения к канонического виду.

Max L=X1+3X2

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

После преобразования любой КЗЛП к канонической всегда получим, что число неизвестный n>m, то есть система уравнений для неотрицательных переменных имеет степень свободы n-m=5-3=2.

Поиск решения системы для которой n>m.

Для решения такой системы необходимо задать n-m переменных, которые называются небазисными, независимыми, сободными, а остальные M ПЕРЕМЕННЫХ получить из решения системы эти переменные называются базисными (зависимыми, не свободными). Пусть…

Если взять в качестве небазисных X1=2 и X2=3, отсюда получаем базисные Х3=30-6*2-5*3=3, Х4=6-2-6=-2, Х5=4. Точка с координатами 2 и 3 недопустима, так как второй ресурса не хватает (слековая переменная отрицательна). Для поиска угловой точки, следует воспользоваться следующим свойством (теорема об алгебраическом характере угловой точки).

Пусть есть КЗЛП n>m, тогда решение системы Ах=b дает угловую точку, тогда и только тогда, когда оно опорное. Решение называется опорным, если оно не отрицательное (допустимое и базисное).

Решение называется базисным, если небазисные переменные в количестве n-m=0.

Для любой системы число базисных решений конечное

….*** НАЙДЕМ БАЗИСНОЕ, ВЫБЕРЕМ ОПОРНОЕ,А ИЗ ОПОРНЫХ ОПТИМАЛЬНОЕ

Составим все возможные комбинации…

Всего таких комбинаций

Аналогичным образом можно получить все 10 базисных решений и выбрать из них 5 угловых точек, а именно

Подставим

Точка К для канонической задачи, является оптимальной точкой (аналогично на графике), для неё Х1=0, Х2=3. Слековые переменные Х3=15, Х4=0, а сурклассовая Х5=2. При этом небазисная переменная (образующая угловую точку) Х4=0 и Х1=0, т.е. выпускается только второй продукт в количестве трех единиц, при этом первый ресурс в избытке 15 единиц, второй ресурс истрачены все 6 единиц,а превышение над уровнем единицы составляет двойка.

Если есть задача каноническая и у неё есть оптимальное решение, то у этой задачи, обязательно найдется оптимальная точка – угловая, когда не нулевых переменных будет не больше n, т.е. если в задачи экономики и управления есть m ограничений любого вида, а неизвестных m продуктов которых нужно выпустить,то из n продуктов выпускаться в оптимальном плане будет выпускаться не больше m.

Пусть предприятие выпускает 15 продуктов, используя 4 ресурса, тогда из 15-ти следует выпускать не больше 4-ех.

Или в транспортной задачи, пусть у Вас 10 поставщиков и 20-ть потребителей (всего путей 200),в оптимальном плане будет задействовано не больше, чем (10+20-1) 29 путей.

Теорема о алгебраической характеристики угловой точки позволяет заранее сказать о числе нулей в решении, то есть о количестве рентабельных и не рентабельных продуктов.

Метод перебора угловых точек.

1. Из канонических соображений убеждаемся что задача имеет оптимальное решение, чтобы не попасть в ситуацию III.

2. Приводим к задачам КЗЛП.

3. Ищем все базисные решения С_n^m

4. Из них выбираем неотрицательные – опорные угловые.

5. Из угловых выбираем наилучшую по функции цели.

ДЗ

Задание номер один

Задача по варианту, показать область допустимых значений, написать координат угловой точки.

Дата добавления: 2014-01-03