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)


 

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

29772. Диэлектрические материалы 37.85 KB
  Пассивные – это электроизоляторные и конденсаторные материалы. Пассивные неорганические диэлектрики применяемые в электронной технике можно разделить на стекловидные диэлектрики керамику монокристаллические диэлектрические материалы органические и композиционные материалы. Активные диэлектрики – это материалы свойствами которых можно управлять в широких пределах с помощью внешних воздействий.
29773. Классификация и особенности материалов электронной техники. Структура материалов. Обозначение кристаллографических плоскостей и направлений кристалла 25.27 KB
  Структура материалов. Классификация и особенности материалов электронной техники. Электрофизические свойства являются одним из основных свойств материалов определяют их применение в электронной технике.
29774. Способы представления сложных структур. Типичные кристаллические структуры материалов, применяемых в электронной технике 87.11 KB
  Структура типа алмаз. Элементарные полупроводники кремний и германий кристаллизуются в структуру типа алмаз. В структуре типа алмаз атомы образуют плотнейшую ГЦК решётку в которой половина 4 из 8ми тетраэдрических пустот заняты атомами того же сорта. Структура типа алмаз может быть представлена как две взаимно проникающие подрешётки типа ГЦК которые смещены относительно друг друга по пространственным диагоналям на её длины.
29775. Дефекты в кристаллах. Классификация дефектов. Точечные, линейные и поверхностные дефекты 30.5 KB
  Линейные дефекты К линейным дефектам кристаллической решётки относятся дислокации. Различают краевые и винтовые дислокации. Линия дислокации в этом случае – это граница экстраплоскости. Винтовую дислокацию в кристалле можно определить как сдвиг одной части кристалла относительно другой но в отличие от краевой дислокации линия винтовой дислокации параллельна вектору сдвига.
29776. Цепь посылки вызова от ТА-57 на станцию ЦБ по структурной схеме 210.5 KB
  Кроме того оборудование комплекса позволяет образовать типовые каналы ТЧ 03 34 кГц каналы служебной связи 16; 192; 2275 кбит с прозрачные телеграфные каналы до 200 бод а также синхронные контрольные каналы 2037 и 4074 бит с. Кроме указанных выше цифровых каналов на каждой ступени образуются следующие дополнительные каналы: прозрачные телеграфные каналы ПТК; служебные телеграфные каналы СТК; синхронные контрольные каналы СКК; синхронные каналы служебной связи СКСС. Телеграфные каналы образуемые комплексом...
29777. Цепь дистанционного управления радиостанцией П-193М по структурной схеме 37.5 KB
  В качестве каналообразующей аппаратуры применяется аппаратура П331 П331МСкорость цифрового сигнала поступающего с аппаратуры П331 П331М может составлять 48 480 и 2048 кбит с.3 мкм; код линейного сигнала СМI; линейная скорость передачи 2048 кбит с независимо от скорости передачи входного сигнала; скорость передачи канала УСС 48 кбит с с ЭППЧ 03 21 кГц; Структурная схема аппаратуры П336Л. Цифровой сигнал от аппаратуры каналообразования ЦСП П331 П331М со скоростью передачи 48 кбит с ИО2 ИТ А или 480 кбит с...
29778. Назначение, ТТХ и состав (по общей схеме) телефонного коммутатора П-194М 149 KB
  Основные ТТХ П194М Число абонентских линий: П194М рассчитан на включение 40 абонентских линий в том числе: 3 соединительных линий линий № 3840 к станциям ЦБ или АТС; 10 соединительных линий линий № 1120 к радиостанциям УКВ с дистанционным управлением; 20 соединительных линий линий к КОА ДС с возможностью включения и выключения удлинителей. На вертикальной лицевой панели коммутатора размещены: пять вертикальных плат с 40 абонентскими комплектами; платы с гнездами для циркулярных соединений; ключи комплектов...
29779. Цепи вызова абонентом и опроса вызывающего абонента П-194М по принципиальной схеме 49 KB
  Вопрос 1. Цепи вызова абонентом и опроса вызывающего абонента П-194М по принципиальной схеме. Назначение и основные ТТХ радиорелейной станции Р-409МА. Состав ВЧ оборудования Р-409МА, назначение блоков. Опрос абонента коммутатора П-194М.
29780. Цепь прохождения разговора между двумя абонентами П-194М по принципиальной схеме 474 KB
  2: При работе станции в поддиапазоне А частоты возбудителя лежат в пределах 60120 мГц а в поддиапазонах Б и В – в пределах 6011199 мГц. В сменных блоках передатчиков обеспечивается или только усиление А или усиление и умножение частоты колебаний возбудителя Б В. Отличие заключается лишь в том что в приемниках поддиапазонов Б и В дополнительно применено соответственно удвоение и учетверение частоты первого гетеродина блока Б2 общего для трех поддиапазонов станции. Как видно из рисунков в приемниках применено двойное...