40140

Приведение задач линейного программирования к каноническому виду. Методы искусственного базиса

Доклад

Менеджмент, консалтинг и предпринимательство

Основная теорема ЛП: если задача ЛП имеет решение то целевая функция достигает экстремального значения хотя бы в одной из угловых точек многоугольника решений. Таким образом с теоретической точки зрения решение задачи ЛП выглядит следующим образом: можно найти все угловые точки многоугольника решения высчитать в них значение ЦФ выбрать наибольшее наименьшее. процесс нахождения угловых точек сравним по трудности с решением исходной задачи. В этом заключается основная идея СМ которая предполагает: 1 уметь находить первоначальное базисное...

Русский

2013-10-15

66 KB

20 чел.

16. Приведение задач линейного программирования к каноническому виду. Методы искусственного базиса.

Задача ЛП имеет вид:

    (1)

Если в ограничениях с bi стоят только неравенства, то говорят, что задача задана в стандартной форме.

Если стоят только равенства, то в канонической форме.

Множество всех решений, удовлетворяющих всем ограничениям (1), называется множеством допустимых решений. Это множество с геометрической точки зрения представляет собой некоторый выпуклый многоугольник или выпуклую многоугольную область решений.

Основная теорема ЛП: если задача ЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из угловых точек многоугольника решений.

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

Точка называется внутренней, если окрестность этой точки, которая принадлежит целиком данному множеству.

Точка называется граничной, если в окрестности этой точки содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие множеству

Точка называется угловой, если она не является внутренней не для какого отрезка, целиком принадлежащего данному множеству

Если ЦФ достигает ext в более чем в одной точке, то она достигает того же значения в точке, являющейся их линейной выпуклой комбинацией.

Таким образом, с теоретической точки зрения решение задачи ЛП выглядит следующим образом: можно найти все угловые точки многоугольника решения, высчитать в них значение ЦФ, выбрать наибольшее / наименьшее.

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

Поэтому способ целенаправленного перебора угловых точек. Суть: в начале находят одну из угловых точек, при этом надо иметь критерий остановки перебора. Если начальная точка не удовлетворяет этому критерию, то надо иметь критерий перехода к нехудшей точке, в которой значение функции не меньше при нахождении max, не больше при min, чем в предыдущей точке.

В этом заключается основная идея СМ, которая предполагает:

1) уметь находить первоначальное базисное решение

2) критерий оптимальности базисного решения

3) критерий переходить к «нехудшему» базисному решению

Пусть имеем канонический вид:

    (2)

Канонический вид всегда можно получить из стандартной определенными способами (добавление / вычитание дополнительных переменных).

Система уравнений в (2) в случае ее совместности и ранга = m имеет некоторый базис, содержащий m векторов, через которые можно выразить другой вектор Ai, составленный из коэффициентов aij.

Переменные xi, соответствующие базисным векторам, называются базисными, остальные (nm) переменных – свободными.

Базисным решением m линейных уравнений с n переменными называется решение, в котором все свободные = 0, если при этом все xi  0, то базисное решение называется допустимым

Допустимое базисное решение – решение, в котором все свободные = 0, а базисные равны свободным элементам.

Каждому допустимому базисному решению соответствует одно угловая точка. Поэтому для того чтобы найти первую угловую точку надо уметь находить некоторое допустимое базисное решение.

Ограничение имеет предпочтительный вид, если левая часть ограничения содержит переменную с коэффициентом 1, которая в остальные ограничения вводится коэффициентом 0.

Если каждые ограничения имеют предпочтительный вид, то система ограничений называется предпочтительной.

В этом случае базисные решения находит так: приравниваем к 0 непредпочтительные переменные, тогда предпочтительные переменные будут равны соответствующим значениям правой части, которой по определению 0. Таким образом, получаем допустимое базисное решение. Предпочтительные переменные будут базисными, а непредпочтительные – свободными.

а) Предположим, что система ограничений имеет вид:

   (3)

Введем дополнительные неотрицательные переменные так, чтобы неравенства превратились в равенства. (3) имеет предпочтительный вид. В качестве базисных переменных возьмем дополнительные, в качестве свободных – исходные переменные. Допустимое базисное решение в этом случае имеет вид:

б) Предположим, что система ограничений имеет вид:

   

Если введем дополнительные неотрицательные переменные, то получим систему:

    (4)

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

В этом случае использует один из 2 методов искусственного базиса.

I метод искусственного базиса

К левым частям ограничения (4) добавляют неотрицательные искусственные переменные wi.

В ЦФ искусственные переменные вводятся с коэффициентом +М в случае нахождения min и с коэффициентом -М в случае нахождения  max.

Полученная задача всегда имеет предпочтительный вид. Такая задача называется М-задачей.

Предположим,  в системе ограничений (2) все ограничения имеют непредпочтительный вид. Составим М-задачу при указанном положении:

 

M – большое положительное число.

ЗАМ: если имеются предпочтительные ограничения, то добавлять в него wi не надо.

Теорема: если в оптимальном решении X* = (x1, …, xn, w1, …, wm) М-задачи все искусственные переменные wi = 0, то решение X = (x1, …, xn) является оптимальным решением для исходной задачи (2).

II метод искусственного базиса

Рассмотрим задачу (2) с ограничениями типа (4):

    (5)

Предположим,  система (5) не имеет не предпочтительный вид. Введем искусственные переменные wn+1, …, wn+m так, чтобы (5) принял предпочтительный вид. (Если какое-нибудь равенство k в (5) имеет предпочтительный вид, то искусственную переменную wn+k либо не вводим, либо считаем wn+k = 0).

Составим следующую задачу:

     (6)

Теорема: пусть задача (5) имеет допустимое решение. Решение X* = (x1, …, xn, wn+1, …, wn+m) задачи (6) является оптимальным  wn+i = 0,  i = 1..m.

Теорема гарантирует равенство 0 всех искусственных переменных в оптимальном решении X*  X = (x1, …, xn) является допустимым решением задачи (5), но, вообще  говоря, оно не является оптимальным решением задачи, как это было в случае I метода искусственного базиса.

Однако на практике II метод имеет следующее применение. Предположим, оптимальное решение X* задачи (6)  найдено СМ. Тогда ненулевым компонентам X* соответствуют линейно независимое векторы Aj. Так как ненулевыми компонентами по теореме могут быть только исходные переменные xj, а не искусственные wn+i, то решению X* соответствуют линейно независимые векторы из системы Aj. Если оказалось, что оптимальное решение X* не вырождено, то число линейно независимых векторов составляет базис. Этот базис и соответствующие ему переменные xj могут быть приняты в качестве первоначального допустимого базисного решения задачи (5).

Таким образом, алгоритм  метода:

  1.  задача (5) преобразуется в (6)
  2.  задача (6) решается СМ.
  3.  если решение X* не вырождено, то в последней таблице СМ вычеркиваются столбцы, соответствующие искусственным переменным и пересчитывается j. Полученная таблица будет являться исходной для решения задачи (5)


 

А также другие работы, которые могут Вас заинтересовать

30746. США и Латинская Америкак: эволюция и проблемы взаимоотношений во второй половине 20 столетия 26.5 KB
  Во время Второй мировой войны создались благоприятные условия для развития национального капитала в Латинской Америке. Выросли цены на сырье ослабло влияние национального капитала увеличились средства для вложения в национальную промышленность. Новый уровень глобализации иначе говоря огромная роль мировых хозяйственных связей привлечение современной технологии и иностранного капитала стал частью стратегии латиноамериканских стран. Основным источником накопления капиталов и модернизации стали широкое привлечение иностранного...
30747. Причины зарождения и сущность фашизма 24 KB
  в конкретной исторической обстановке фашизм нужен определенным кругам империализма чтобы справиться с возрастанием революционного движения разрешить в свою пользу классовые противоречия которые нельзя разрешить старыми методами и формами борьбы. Мировому капиталу фашизм был нужен чтобы разрушить главной оплот международного революционного процесса и антиимпериалистической борьбы – СССР. Германский фашизм сопровождался политическими убийствами погромами и др.
30748. Латинская Америка: что принесли неолиберальные преобразования (на опыте 1980 - 1990-х гг.) 27 KB
  стимулировал экономический рост Латинской Америки в начале 90х гг. Другая болевая точка современной Латинской Америки безработица принявшая беспрецедентные масштабы. Финансовоэкономическая стратегия Латинской Америки на 90е гг. В задачи консенсуса входило преодоление инфляции сокращение бюджетного дефицита укрепление национальных валют Латинской Америки.
30749. Причины и характер первой мировой войны, цели воюющих сторон. (28 июля 1914 — 11 ноября 1918) 23.5 KB
  28 июля 1914 11 ноября 1918 стремление к переделу мира в результате противостояния двух военных блоков: Тройственного Союза Германия АвстроВенгрия Италия и Антанты Англия Франция Россия борющихся за гегемонию на континенте. слабое рабочее движение в результате в ряде стран победили партии войны в правящих кругах ряда Западных стран Германия Великобритания АвстроВенгрия и Франция. Цели: Германия – создать Новую Европу где влияния Англии Франции и России свелись бы к нулю. АвстроВенгрия как и Германия за...
30750. Бетонирование колонн, стен, перекрытий 14.54 KB
  При возведении стен в разборнопереставной опалубке смесь укладывают участками высотой не более 3 м. В стены толщиной более 05 м при слабом армировании подают бетонную смесь подвижностью 4. Бетонную смесь подают непосредственно в опалубку в нескольких точках по длине участка бадьями виброжелобами бетононасосами. При высоте стен более 3 м используют звеньевые хоботы при этом смесь укладывают горизонтальными слоями толщиной 03.
30751. Назначение и виды опалубок. Требования к опалубке. Оборачиваемость опалубных форм 16.57 KB
  Поверхность опалубки непосредственно примыкающая к бетону должна быть плотной иметь малую с бетоном адгезию и не иметь щелей чтобы не вытекало цементное молоко. Важнейшим показателем качества опалубки является ее оборачиваемость т. Применение инвентарной многооборачиваемой опалубки из унифицированных элементов с модульным изменением размеров и укрупненных блоков способствует снижению трудоемкости и стоимости опалубочных работ. Для изготовления опалубки используют доски из древесины II III и IV сортов хвойных пород допускается...
30752. Разборно-переставная опалубка. Область применения, конструкция 15.58 KB
  Технологический процесс устройства опалубки состоит в следующем. Щиты опалубки или собранные из них крупные опалубочные элементы устанавливают вручную или краном и закрепляют в проектном положении. Масса элемента этой опалубки до 70 кг. Щиты опалубки изготовляют из досок толщиной 19.
30753. Объёмно-переставная опалубка. Конструкция, область применения 17.24 KB
  Секции при соединении образуют туннели опалубки на квартиру или на всю ширину здания. Секции опалубки могут иметь переменную ширину в зависимости от принятого шага стен и различную длину. П и Гобразные секции опалубки устанавливают на перекрытии ранее забетонированного этажа выверяют и закрепляют между собой в продольном и поперечном направлениях. Общие конструктивные признаки опалубки: наличие системы механических домкратов для выверки и установки в проектное положение; катучие опоры для перемещения секций опалубки при монтаже и...
30754. Скользящая опалубка. Технология бетонирования стен в скользящей опалубке 14.52 KB
  При бетонировании следят за вертикальностью домкратного стержня и за бетонной поверхностью Применение скользящей опалубки особенно эффективно при строительстве высотных зданий и сооружений с минимальным количеством оконных и дверных проемов конструктивных швов и закладных элементов. К ним относятся силосы для хранилища материалов дымовые трубы и градирни ядра жесткости высотных зданий резервуары для воды радиотелевизионные башни. Другая потенциальная область использования скользящей опалубки строительство зданий атомных реакторов...