- •Предметы и задачи курса.
- •Основные задачи и модели, используемые в математическом программировании.
- •Модель этой задачи.
- •Вторая задача: Задача о содержании.
- •Задача о смеси
- •Задача о смеси линейная
- •Поиск угловых точек
- •Универсальный способ решения злп-симплекс метод
- •Реализация принципов симплекс метода для канонической задачи
- •Алгоритм симплекс-метода
- •Построение двойственной задачи
- •Оптимальное решение двойственной задачи
- •Пример работы с двойственностью и чувствительностью.
Поиск угловых точек
Каноническая задача линейного программирования
Для удобства поиска угловых точек в задачу линейного программирования следует приводить к каноническому виду (КЗЛП).
КЗЛП – jxj
Это задача на максимум 1, для не отрицательных переменных это 3-ка, в этой задаче n-переменных и m-равенств.
Любую ЗЛП можно привести к эквивалентвоной КЗЛП (решения которых одинаковые)
Переход к КЗЛП
Переход от минимума к максимуму
Min L=3X1+5X2-6X3
Max L*=-3X1-5X2+6X3
L=L*
Переход от неравенства к равенству.
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 путей.
Теорема о алгебраической характеристики угловой точки позволяет заранее сказать о числе нулей в решении, то есть о количестве рентабельных и не рентабельных продуктов.
Метод перебора угловых точек.
Из канонических соображений убеждаемся что задача имеет оптимальное решение, чтобы не попасть в ситуацию III.
Приводим к задачам КЗЛП.
Ищем все базисные решения Сnm
Из них выбираем неотрицательные – опорные угловые.
Из угловых выбираем наилучшую по функции цели.
ДЗ
Задание номер один
Задача по варианту, показать область допустимых значений, написать координат угловой точки.