АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Линейные неравенства. Графический метод линейного программирования

Читайте также:
  1. A) линейные
  2. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  3. I. Методические основы
  4. I. Предмет и метод теоретической экономики
  5. II. Метод упреждающего вписывания
  6. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
  7. II. Методы непрямого остеосинтеза.
  8. II. Проблема источника и метода познания.
  9. II. УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА ДИСЦИПЛИНЫ
  10. III. Методологические основы истории
  11. III. Предмет, метод и функции философии.
  12. III. Социологический метод

Пусть в уравнении прямой (4) знак равенства заменен знаком неравенства ³ или £; соответствующее множество точек M(x; y) называется полуплоскостью.

Например, линейное неравенство y ³ 2 x + 3 описывает полуплоскость, состоящую

из всех точек на или выше (левее) прямой y = 2 x + 3. Аналогично, x ³ 0 - это

неравенство для полуплоскости, состоящей из точек на или правее оси O y.

Системы линейных неравенств находят применение в так называемых задачах линейного программирования. Рассмотрим конкретный (двумерный) пример.

Пример. Пусть некоторое множество состоит из всех точек на плоскости, координаты которых удовлетворяют системе линейных неравенств (10.а) – (10.д).

Все точки плоскости,удовлетворяющиеданной системе неравенств, называются планами. Кроме того, задана линейная функция z = 2 x + 3 y, называемая целевой функцией. Задача ставится так: найти наибольшее значение (максимум) целевой функции на множестве планов. Также следует указать оптимальный план M0 (x 0 ; y 0), на котором целевая функция принимает максимум. (Аналогично формулируется задача на минимум целевой функции.)

Решение задачи графическим методом. Множество всех планов состоит из точек, удовлетворяющих сразу всем 5 условиям: эти точки расположены (a) на или ниже прямой y - x =2, (б) на или ниже прямой 3 y + x = 14, (в) на или выше прямой y - 3 x= -12,(г) на или правее прямой x = 0,(д) на или выше прямой y = =0. Отсюда следует, что множество планов есть выпуклый 5-угольник OA1A2A3A4. Каждая его вершинанаходится на пересечении пары прямых, ограничивающих 5-угольник. Например, на пересечении прямых y - x = 2, x = 0 находится вершина A1; на пересечении прямых yx = 2, 3 y + x = 14 находится вершина A2. Аналогично определяются вершины A3, A4, O.

Множество точек M(x; y), на которых целевая функция принимает некоторое постоянное значение, называется линией уровня для z. Все линии уровня представляют собой параллельные прямые, задаваемые уравнениями 2 x +3 y = c.

Рассмотрим одну из этих прямых 2 x + 3 y = 0 (здесь c= 0, целеваяфункция z

также равна 0). Это прямая LO с угловым коэффициентом k = - 2 / 3.Другие линии уровня получаются параллельным перемещением прямой LO. Этот сдвиг прямой можно производить с помощью линейки. При сдвиге линейки вправо (или вверх) значение c целевой функции увеличивается. Например, прямая L1 - линия уровня, проходящая через вершину A1. Линейку можно сдвигать вправо (или вверх) до тех пор, пока на соответствующей линии уровня находятся точки 5-угольника. В итоге достигается крайняя точка, которая и будет оптимальным планом. Это - вершина 5-угольника, характеризуемая тем, что линия уровня, проходящая через нее, не имеет общих точек с внутренностью 5-угольника. В данном случае, как видно из рисунка, эта вершина есть A3(5; 3), координаты которой x 3 = 5, y 3 = 3 находятся из системы уравнений 3 y + x = 14, y - 3 x = -12. Значение целевой функции для этого плана есть z = 2 x 3+3 y 3=2 × 5 + 3 × 3 = 19. Ответ: z max = 19, оптимальный план M0 (5; 3).

Правило проверки. Существует простой числовой метод, который позволяет подобрать оптимальный план или проконтролировать правильность подобранного оптимального плана. Рассмотрим более общую целевую функцию z = a 1 x + a 2 y, для которой нужно найти максимум. По знакам чисел a 1 , a 2 уже можно указать те части границы многоугольника, где следует искать оптимальный план.

a 1> 0, a 2> 0: П Ç В a 1> 0, a 2 < 0: П Ç Н a 1 < 0, a 2> 0: Л Ç В a 1 < 0, a 2< 0: Л Ç Н

Здесь П,Л,В,Н – это правая, левая, верхняя, нижняя части границы многоугольника. (Например, верхняя часть границы, В, состоит из всех верхних точек сечений многоугольника вертикальными прямыми.) Остановимся подробнее на двух случаях.

1-я ситуация. Пусть коэффициент a 2 > 0, тогда оптимальный план является вершиной на верхней части границы многоугольника планов. В рассмотренном примере верхняя часть границы – это ломаная линия A1A2A3, выпуклая вверх. Угловые коэффициенты k 12и k 23 сторон A1A2 и A1A2 ломаной линии убывают при обходе верхней границы слева направо: k 12 > k 23 . Если угловой коэффициент k = - a 1/ a 2 линии уровня z = c расположен на полуинтервале k ³ k 12, то вершина A1 -

оптимальный план. Если k 12³ k ³ k 23, то вершина A2 –оптимальный план. Если k 23 ³ k, то вершина A3 – оптимальный план.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)