ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ




РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ.

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

Система линейных неравенств имеет вид:

a11 x1 + a12 x2 +…+ a1n xn < b1

a21 x1 + a22 x2 +…+ a2n xn < b2

………………………………

am1 x3 + am2 x2 +…+ amn xn < bm

 

Кроме знака «<» в записанных неравенствах могут исполь­зоваться и другие знаки: «>», « », « ». В случае двух перемен­ных система принимает вид

a11 x + a12 y < b1

a21 x + a22 y < b2

………………...

am1 x + am2 y < bm

 

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

Системы линейных неравенств достаточно часто используются при построении математических моделей экономических процессов. Обычно такие неравенства ограничивают об­ласть изменения определенных параметров, оказывающих влияние на искомый результат. В частности речяы/ь может идти об эффективном использовании некоторого ограниченного запаса ресурсов с целью получения максимальной прибыли или минимизации затрат на производство. Естественно, из­меняя в допустимых пределах параметры производства (объем выпуска продукции каждого вида, запасы сырья, трудовые ре­сурсы и т.п.), можно получить значительное количество вари­антов решения, среди которых надо выбрать оптимальный. Методы решения задач на экстремум функции с многими пе­ременными при наличии некоторых ограничений на область изменения этих переменных изучает специальный раздел ма­тематики – математическое программирование. Функция, максимум (минимум) которой требуется при этом найти, на­зывается целевой функцией. Если во всех ограничениях и в це­левой функции переменные содержался только в первой сте­пени, имеем задачу линейного программирования, при более высоких степенях – задачу нелинейного программирования.

В общем виде задача линейного программирования формулируется следующим образом: найти максимум (мини­мум) целевой функции

 

при условиях

 

a11 x1 + a12 x2 +…+ a1n xn a10

a21 x1 + a22 x2 +…+ a2n xn a20

………………………………

ak1 x1 + ak2 x2 +…+ akn xn ak0

 

 
 


a (k+1)1x1 + a(k+1)2 x2 +…+ a(k+1) n xn=a(k+1)0

………………………………………………..

a m1x1 + am2 x2 +…+ am n xn=am0

 

x1 0

x2 0

……..

xp 0(p

 

В симметричной форме задача линейного программирования запишется так: найти максимум (минимум) целе­вой функции

 

при условиях

 

 
 


a11 x1 + a12 x2 +…+ a1n xn a10 x1 0

a21 x1 + a22 x2 +…+ a2n xn a20 x2 0

……………………………….……

am1 x1 + am2 x2 +…+ amn xn am0 xn 0

 

 

Набор чисел (x1, x2,…,x п), удовлетворяющих указанным условиям, называют планом. Среди всех возможных планов может существовать оптимальный план (x1*, x2*,…, x п *), дающий целевой функции максимальное (минимальное) зна­чение.

Для решения задачи линейного программирования с дву­мя переменными можно использовать графический метод. В этом случае задача принимает вид

 

при условиях

a11 x1 + a12 x2 a10

a21 x1 + a22 x2 a20

………………….

am1 x1 + am2 x2 am0

x1 0, x2 0

 

При использовании графического метода в плоскости (x1, x2) строится область допустимых решений задачи, опре­деляемая условиями, и вектор с = (с1, с2), который будет по­казывать направление наискорейшего возрастания функции f (соответственно вектор - с будет показывать направление наискорейшего убывания). если на плоскости построить семей­ство параллельных прямых, перпендикулярных к вектору с, то для всех точек каждой из таких прямых f = const. Напри­мер, для прямой, перпендикулярной к вектору с и проходя­щей через начало координат. f = 0 (рис. 14). Искомая точка максимума находится перемещением прямой f = const в на­правлении вектора с параллельным образом. Максимума фун­кция достигнет в последней точке области допустимых реше­ний, через которую пройдет перемещаемая прямая f = const (на рис. 14 - это точка А). Аналогично перемещением пря­мой в противоположном направлении находится минимум функции.

 

X1  
A
X2  

 

Рис. 1. Графический метод решения задачи линейного программирования с двумя переменными.

РЕШЕНИЕ ТИПОВЫХ ЗАДАЧ

 

1. Решите систему линейных неравенств

 

x1 + x2 6

x1 + 2x2 > 6

x1 0

 

Решение. Покажем вначале на координатой плоскости множество точек, удовлетворяющих первому неравенству. Для этого построим прямую x1 + x2 = 6 по двум точкам:

 

X1    
X2    

Эта прямая разбивает координатную плоскость на две по­луплоскости, одна из которых и будет содержать точки, удов­летворяющие данному неравенству. Для того чтобы опреде­лить, какая из двух полуплоскостей содержит точки - реше­ния неравенства, подставим в это неравенство координаты точки 0 (0, 0): 0 + 0 < 6. т.е. оно верно. Следовательно, речь идет о полуплоскости, содержащей точку 0 (0, 0). На рис. 15, а она заштрихована. Поскольку точки, принадлежащие прямой x1 + x2= 6, также являются решением неравенства х1 + х2 6, прямая изображена на рисунке сплошной линией. (Если бы неравенство имело вид x1 + x2<6, то точки прямой не входи­ли бы в множество решений и ее следовало бы изобразить пунктирной линией.) Обычно, чтобы не загромождать рису­нок, штрихуют не всю полуплоскость, а только ее небольшую часть, прилегающую к прямой, как это показано на рис. 15, б. Аналогично ищем решения неравенств x1 + 2x2 > 6 и x1 0, предварительно построив по двум точкам графики со­ответствующих прямых:

 

 

x1 + 2x2 = 6 И x1 = 0
X1     X1    
X2     X2    

 

 

X1
X1
b
a
X2
X1+X2=6
X2
X1+X2=6

 

Рис. 2 Множество решений неравенства X1+X2 6

 

При этом следует учитывать, что график прямой х1 + 2x2 = 6должен быть изображен пунктирной линией, так как точки данной прямой не являются решениями неравенства х1 + 2x2 > 6 (рис. 16).

 

 

X1=0
х1 + x2 = 6
х1 + 2x2 = 6

Рис. 3

Решениями системы неравенств будут все точки плос­кости, в которой пересекаются три штрихованные области. Как следует из рисунка, это будут точки, принадлежащие области АВС. причем точки, лежащие на отрезках АС и АВ, входят в множество решении неравенства, а точки отрезка ВС -нет.

2. Предприятие выпускает продукцию двух видов А и В, для производства которых требуетсясырье трех видов M, N, P, в следующих количествах:

Вид сырья Потребности сырья, т. Для производства 1 т. продукции вида
А В
M    
N    
P    

 

Запасы сырья М составляют 140 т, N - 150 т, Р - 180 т. Продажа 1 т продукции вида А дает прибыль 2 у.е., продукции вида В – 3у.е. Определите, какое количество продукции вида А и В следует выпускать предприятию для получения макси­мальной прибыли.

Решение. Обозначим через x1 объем производства продукции вида А, а черезx2 – объем производства продукции ви­да В. Тогда прибыль от реализации продукции вида А составит 2x1, а от реализации продукции вида В - 3x2. Общая прибыль предприятия в этом случае

 

f =2x1+3x2àmax

 

ограничения па затраты сырья запишутся в виде

 
 


x1 + 2x2 140

3x1 + x2 150

3x1 + 2x2 180

x1 0, x2 0

 

Последние дна неравенства показывают, что количество вы­пушенной продукции не может быть отрицательным числом.

Для применения графического метода решения задачи па координатной плоскости построим графики прямых

x1 + 2x2 = 140, 3x1 + x2 = 150, 3x1 + 2x2 = 180, x1= 0, x2= 0.

 

Прямые строим по двум точкам:

 

x1 + 2x2 = 140   3x1 + x2 = 150   3x1 + 2x2 = 180
x1       x1       x1    
x2     x2     x2    

 

Далее по аналогии с предыдущей задачей находим область допустимых решений (рис. 17). Затем строим вектор с = (2, 3) и перпендикулярно к нему линию нулевого уровня. Перемещая полученную линию параллельным образом, находим точку, в которой целевая функция достигает максимума. Этобудет точка В; она является последней точкой области, ка­сающейся перемещаемой линии. Найдем её координаты:

 

x1 + 2x2 = 140

3x1 + 2x2 = 180

 

3x1+2x2=180
x1+2x2=140
3x1+x2=150

Рис. 4

Решая данную систему, находим координаты точки В: x1=20, x2=60.

Таким образом, максимальная прибыль будет достигнута при плане выпуска продукции вида А 20 т и продукции вида В 60 т. При этом прибыль составит

 

СИМПЛЕКС МЕТОД



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-02 Нарушение авторских прав и Нарушение персональных данных


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