Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Переход от стандартной и общей форм ЗЛП к канонической
Разнообразие форм задач линейного программирования затрудняет исследование их общих особенностей и создание общих методов и вычислительных алгоритмов для их решения. Рассмотрим способ сведения любой ЗЛП к наиболее простой и удобной для исследования форме — канонической. Для осуществления перехода от стандартной формы записи к канонической нужно в каждое из m неравенств системы ограничений ввести m дополнительных неотрицательных переменных: xn+1, xn+2,…, xn+m, тогда система ограничений примет вид: allx1+a12x2+... + a1nxn+ xn+1 = b1 a21x1+a22x2+ + a2nxn + xn+2 = b2 (1.5.14) а31х1+а32х2+... + азnхn + xn+3 = b3 ………………………………………… am1х1+аm2х2+... + аmnхn+ xn+m = bm здесь xn+1, xn+2, xn+3, …, xn+m— выравнивающие балансовые переменные, где xj ≥0, где (j = l,...,n+m). Добавив эти балансовые переменные в неравенства, превращаем их в уравнения. Если же в стандартной форме требовалось минимизировать целевую функцию, то, заменив ее знак на «-», получим: F1 = F = -c1 х1 - c2 х2 - c3 х3 -…..- cn хn → max (1.5.15) Для решения этой задачи необходимо найти такой вектор Х=(x1, x2, x3, …, xm), который удовлетворял бы системе ограничений (1.5.14) и при котором целевая функция (1.5.15) принимала бы максимальное значение. Пример Пусть ЗЛП задана в стандартной форме: F = 2х1 + Зх2 → max при ограничениях: х1+Зх2≤18 2x1+x2≤16 х2≤5 Зх1 ≤21 x1≥0; х2≥0. Приведем эту задачу к каноническому виду. Обратим имеющуюся систему неравенств в равенства, вводя для этого в каждое из них соответствующую неотрицательную переменную: x1 +3х2 + х3 =18 2х1 +х2 + х4 =16 х2 + х5 =5 Зх1+ х6 =21. В данном примере все дополнительные переменные введены со знаком «+», так как рассматриваемые неравенства имеют знак ≤. Необходимо заметить, что в том случае, если неравенства имели бы знак ≥, переменные нужно было бы вводить со знаком «-». Графический метод решения ЗЛП Графический метод решения ЗЛП имеет ограниченную область применения. Как правило, этим методом решаются задачи, содержащие не более двух переменных. Пример Найти решение X*=(x*1,x*2), которое удовлетворяет системе неравенств: allx1+a12x2 ≤ b1 a21x1+a22x2 ≤ b2 (1.6.1) а31х1+а32х2 ≤ b3 ………………………………………… am1х1+аm2х2 ≤ bm условиям неотрицательности переменных: х 1 ≥ 0, х 2 ≥ 0 (1.6.2) и которое доставляет оптимальное значение целевой функции:
F = c1x1+c2x2 —>max(min). (1.6.3) Применение геометрического метода предполагает использование нескольких этапов. На первом из них в системе координат X1OX2 строится область допустимых решений задачи (ОДЗ). Для этого ка ждое из неравенств системы (1.6.1) заменяем равенством и строим соответствующие этим равенствам граничные прямые: ailx1+ai2x2 = bi (i=l,…, m). Каждая из этих прямых делит плоскость Х1ОХ2 на две полуплоскости (рис. 1.6.1). Для точки (*) А, принадлежащей одной из этих полуплоскостей, выполняется неравенство: ailx1+ai2x2 < bi (i=l,…, m). для любой (*)В, принадлежащей другой полуплоскости, — противоположное: ailx1+ai2x2 > bi (i=l...m), а для любой из точек, лежащих на граничной прямой, — уравнение: ailx1+ai2x2 = bi (i=l...m).
Рис. 1.6.1. Построение ОДЗ Чтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержащая решения, удовлетворяющие рассматриваемому неравенству, достаточно испытать одну какую-либо точку, например точку с координатами (0,0). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, значит, искомая полуплоскость содержит данную точку и штриховка, выделяющая искомую полуплоскость, обращена в сторону к испытуемой точке. Если же неравенство не удовлетворяется, штриховка, выделяющая искомую полуплоскость, обращена в противоположную от данной точки сторону. Неравенства x1≥0 и х2≥0 также соответствуют полуплоскостям, одна из которых расположена справа от оси ординат, а другая - над осью абсцисс (рис. 1.6.1). Выделив полуплоскости, содержащие решения, удовлетворяющие неравенствам, входящим в рассматриваемую систему, мы определим область, в которой находятся решения, удовлетворяющие всем ограничениям, входящим в рассматриваемую систему неравенств. Именно эта область и есть область допустимых решений задачи. Пример. Необходимо построить область допустимых решений, удовлетворяющую системе неравенств: x1+х2≤ 1 x1-x2≤ -1 х 1 ≥ 0, х 2 ≥ 0 Для этого первое из неравенств обратим в равенство (x1+х2= 1) и построим соответствующую ему граничную прямую. Эта прямая проходит через две точки, координаты которых можно определить следующим образом. Положим, x1=0, тогда получим 0+х2= 1, т. е., х2= 1,а если х2=0, тогда x1+0= 1, т. е.,x1=l, следовательно, граничная прямая на рис. 1.6.2 проходит через точки с координатами (0,1) и (1,0).
Чтобы определить; в какой полуплоскости находят решения, удовлетворяющие первому неравенству, подставим точку с координатами (0,0) в первое неравенство 0+0≤ 1 и убедимся, что точка (0,0) ему удовлетворяет. Следовательно, все решения, удовлетворяющие данному неравенству, находятся в той же полуплоскости, что и точка 0, значит, штриховка, выделяющая полуплоскость, содержащую решения, удовлетворяющие первому неравенству, обращена к точке 0. Затем определим полуплоскость, в которой находятся решения, удовлетворяющие второму неравенству. Для этого второе из неравенств обратим в равенство и построим соответствующую этому равенству граничную прямую. С помощью приема, описанного выше, определим точки, через которые проходит граничная прямая; этими точками будут: (x1=0, х2=1) и (x2=0, x1=-l). Испытав точку 0, увидим, что штриховка, выделяющая полуплоскость, содержащую решения, удовлетворяющие первому неравенству, обращена в сторону, противоположную от 0. Выделим полуплоскости, соответствующие неравенствам: x1 ≥ 0 и х2 ≥ 0. Полуплоскость справа от оси ординат будет соответствовать неравенству x1 ≥ 0, а полуплоскость над осью абсцисс — неравенству х2 ≥ 0. В рассматриваемом примере область допустимых решений состоит из одной точки с координатами (0,1). Рис. 1.6.2. ОДЗ —одна точка В общем случае область допустимых решений систем неравенств (1.6.1) и (1.6.2) может быть: 1. пустой, что означает несовместимость систем неравенств: x1+x2≤3 x1-x2≤4 x1≥0; x2≥0
Рис. 1.6.3. ОДЗ —пуста 2. одной точкой: x1+x2 ≤l x1-x2 ≤-1 x1 ≥0; x2 ≥0
Рис. 1.6.4. ОДЗ — одна точка 3. выпуклым многоугольником: 2x1+x2 ≥2 x1+3х2 ≥3 x1-x2 ≥-1 Зх1-х2 ≤ 6 x1+x2 ≤ 5 x1≥0;х2≥0 Рис. 1.6.5. ОДЗ — выпуклый многоугольник 4. неограниченной выпуклой многоугольной областью: Зх1-2х2 ≥-15 4х1-х2 ≥20 Зх1+х2 ≥30 x1-2х2 ≤20 х1 ≥0;х2 ≥0 Рис. 1.6.6. ОДЗ — неограниченная выпуклая многоугольная область
На втором этапе формируется графическое изображение целевой функции. Уравнение: c1x1+c2x2 =L при фиксированном значении L определяет прямую, а при изменении L — семейство параллельных прямых с параметром L. Вектор С=(с1,с2), перпендикулярный всем этим прямым, показывает направление возрастания параметра L. Так, на рис. 1.6.7. показаны прямые, соответствующие уравнению 2x1+3x2=L при L= -3, 0, 3, 9.
Рис. 1.6.7. Графическое изображение целевой функции Для всех точек, лежащих на одной из этих прямых, функция F принимает одно определенное значение, равное соответствующему значению L. Поэтому рассматриваемые прямые называются линиями уровня для параметра L. Важное свойство линии уровня в том, что при их параллельном смещении в одном направлении уровень (значение L) только возрастает, а при смещении в другом — только убывает.Построим для рассмотренного примера линии уровня и определим направление их возрастания. Чтобы построить вектор C=(c1, с2), можно использовать следующий прием: по оси X1 откладывается значение первой компоненты вектора C1=2, а по оси Х2 — значение второй компоненты С2=3. По найденным координатам строим прямоугольник и находим направление возрастания вектора С. Затем перпендикулярно вектору С строим линии уровня.
Рис. 1.6.8. Определение оптимального решения графическим методом Построив на одном рисунке (рис. 1.6.8) область допустимых решений, вектор С, и перпендикулярную ему одну из линий уровня, можно путем ее параллельного перемещения в направлении, указанном вектором С (или в противоположном), определить точку в области допустимых значений, которая доставляет максимум или минимум целевой функции. На рис. 1.6.8 видно, что в крайнем положении линия уровня проходит через (*)В. При дальнейшем ее перемещении она уже не будет иметь общих точек с областью допустимых решений. Таким образом, искомое оптимальное решение, которое графически соответствует координатам (*)В, можно найти путем совместного решения системы двух уравнений, соответствующих граничным прямым АВ и ВД. Если при тех же исходных данных требовалось бы достичь минимума функции F, то, очевидно, линию уровня пришлось бы перемещать в направлении, противоположном вектору С. В этом случае оптимальное решение, соответствующее минимуму функции F, определялось бы координатами точки (*)0. В зависимости от вида области допустимых решений и положения линий уровня возможны следующие случаи:
ЗЛП имеет единственное решение 1.6.10. ЗЛП имеет альтернат. оптимум (А и В)
|
|||||||
Последнее изменение этой страницы: 2017-02-07; просмотров: 238; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.145.44.118 (0.031 с.) |