2 Графический метод решения задач линейного программирования icon

2 Графический метод решения задач линейного программирования




Скачати 219.36 Kb.
Назва2 Графический метод решения задач линейного программирования
Дата20.09.2012
Розмір219.36 Kb.
ТипДокументи

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


Графический метод решения ЛП удобно применять когда число неизвестных равно двум, или когда число неизвестных n превышает число исходных уравнений-ограничений равно на два. Графическое решение задач ЛП дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения на чувствительность.

Рассмотрим этот метод на примере конкретной задачи.

Формулировка задачи. Фирма «Квант» производит два вида продукции, для которых используется два исходных сырья. Максимально возможные суточные запасы сырья составляют 5 и 8 единиц соответственно. Расходы первого сырья на одну единицу продукции №1 и №2 равны единице. Расходы второго сырья на единицу продукции №2 в два раза выше, чем для производства продукции №1,для которой этот расход равен единице. Маркетинговые исследования показали, что суточный спрос на первый вид продукции не превышает трех единиц, а спрос на второй вид продукции меньше спроса на первый вид продукции не более чем на две единицы в сутки.

Прибыль полученная от продажи единицы первого вида продукции равна двум условным единицам, а второго – трем. Какой должен быть план суточного производства фирмы «Квант» чтобы прибыль от ее реализации была максимальна.

Построение математической модели




  1. Берем в качестве неизвестных х1- количество выпускаемых в сутки единиц первого вида продукции; х2 – второго вида продукции.

  2. Определяем ограничения накладываемые на переменные х1, х2.

Учитывая ограничения на запасы сырья, имеем


х1 + х2 ≤ 5;

x1 + 2x2 ≤ 8.


Учитывая информацию от маркетинговых исследований, на х1 и х2 необходимо положить еще такие ограничения:


х1 ≤ 3;

х1 – х2 ≤ 2.


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


х1≥ 0; х2 ≥0.


  1. Находим целевую функцию.

При допущении независимости объема продаж каждого вида продукции суммарная прибыль равна:


L = 2х1+3х2.


Очевидно, что целевую функцию необходимо максимизировать.

Итак, математическая модель рассматриваемой задачи имеет вид:

Определить такие х1 и х2, которые максимизируют целевую функцию


mахL = 2х1+3х2, (1.6)


при ограничениях




х1 + х2 ≤ 5;

х1 + 2х2 ≤ 8; (1.7)

х1 ≤ 3;

х1 - х2 ≤ 8;

х1 ≥ 0; х2 ≥ 0.


Данная задача является задачей ЛП.

Для решения данной задачи графическим методом (задача содержит только только две переменные) вначале определим область допустимых решений (ОДР), в которой одновременно удовлетворяются все ограничения модели. Искомая ОДР показана на рис.2.1.








Х1

8




























7




























6




























5



























4

























A

3

B C




D



















2 ОДР






















1



















х2

-2

-1

0

1

2

3 E

4

5

6

7







-1

L=0








































L








Рис 2.1.

Условия неотрицательности, х1 и х2 ограничивают ОДР только первым квадрантом. Другие ограничения задают прямые линии, соответствующие знаку равенства левой и правой частей ограничения. Области, в которых ограничения выполняются в виде строгого неравенства, указываются стрелками, направленных в область допустимых решений. Таким образом ОДР – это выпуклый многоугольник ОАВСDE. В каждой точке многоугольника, принадлежащей как его внутренней области, так и его границе, все ограничения (1.7) выполняются одновременно. ОДР содержит бесконечное число точек, но оптимальное решение, обеспечивающее максимум целевой функции (1.6), соответствует одной из вершин многоугольника ОАВСДЕ.

Действительно, если вначале построить целевую функцию


L = 2х1 + 3х2 = 0,

а затем последовательно увеличивать L, то получим параллельные линии (рис. 2.1). Перемещаем параллельно целевую функцию пока она ещё соприкасается хотя бы с одной точкой ОДР. Из рисунка 2.1. видно, что точка Д соответствует оптимальному решению, поскольку при дальнейшем увеличении значения целевой функции, прямая соответствующая ей, перестанет соприкасаться с ОДР.

Таким образом, решением задачи является координаты точки Д:

х1 = 2; х2 = 3.

При этом:

махL = 2х1 + 3х2 = 2*2 + 3*3 = 13.


Кроме случая, рассмотренного в данной задаче, возможны случаи, представленные на рис. 2.2, а, б.





Х1






















Х1








































Д

махL

























































































































L




В




ОДР














































Е














































































































































А







Х2














































L=0




























Х2



а б

Рис.2.2


На рис. 2.2.а показан случай, когда линии уровня целевой функции с1х1 + с2х2 оказывается параллельны стороне СД выпуклого многоугольника ОДР.

При этом максимальное значение целевой функции соответствует как вершине С, так и вершине Д, а также любой точке отрезка СД.

Случай, представленный на рис. 2.2.б, соответствует неограниченной ОДР. При этом целевая функция также неограниченна.

Некоторые выводы полученные при графическом решении задачи ЛП обобщаются и на случай, когда число неизвестных больше двух. Приведем без доказательства следующие теоремы.

Теорема 1. В задаче ЛП допустимое множество решения, если оно существует, является выпуклым многогранным множеством.

Ограниченное многогранное множество называется многогранником

Теорема 2. Целевая функция задачи ЛП достигает своего максимума (минимума) в одной из вершин выпуклого многогранника ОДР.

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

Эти две теоремы, которые имеют хорошее геометрическое представление для случая двух переменных, указывает путь решения задачи ЛП: поскольку число вершин выпуклого многоугольника ОДР конечно, то можно перебрать все вершины, и та, в которой целевая функция достигает максимального (минимального) значения, соответствует оптимальному решению.

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


2.4. Алгебраический метод решения задачи ЛП. Симплекс-метод


Алгоритм симплекс-метода, разработанного Данцигом в 1947г., представлен на рис. 2.3.

Решим задачу, которую мы решили в предыдущем параграфе графическим методом, алгебраическим (симплекс-методом).

Приводим вначале задачу к стандартному виду, когда все ограничения имеют вид равенств:


махL = 2х1 + 3х2;

x1 + х2 + S1 = 5;

x1 + 2x2 + S2 = 8; (1.8)

x1 + S3 = 3;

x1 - x2 + S4 = 2;

x1 ≥ 0; x2 ≥ 0; S1 ≥ 0; S2 ≥ 0; S3 ≥ 0; S4 ≥ 0,

где S1,S2,S3, S4 – дополнительные положительные переменные





Рис.2.3

Для нахождения начального решения (одной из вершин ОДР) еще раз приведем графическое изображение области допустимых решений данной задачи (рис 2.4).

Как видим в каждой вершине ОДР две переменные обязательно равны нулю и при переходе от одной вершине к соседней одна нулевая переменная становится неравной нулю, а ненулевая переменная становится равной нулю (рис. 2.5).








Х1

8










S4=0













7

S2=0
















S1=0

6




























5



























4
















S3=0




A

3

B C




D



















2 ОДР






















1



















х2

-2

-1

0

1

2

3 E

4

5

6

7







-1




















































Рис. 2.4



Вершина ОДР

Нулевые переменные

Ненулевые переменные

О

х1, x1

S1, S2, S3, S4

А

S4, x2

S1, S2, S3, x1

В

S4, S3

S1, S2, x2, x1

С

S1, S3

S4, S2, x2, x1

Д

S1, S2

S4, S3 ,x2, x1

Е

х1, S2

S4, S3, х2, S1


Рис. 2.5


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

Все допустимые экстремальные решения, соответствующие вершинам ОДР, определяют как все однозначные неотрицательные решения системы m уравнений, в которых n-m переменных равны нулю.

Однозначное решение такой системы уравнений, получаемые путем приравнивания к нулю (n-m) переменных, называется базисным решением, а соответствующие переменные – базисными переменными. Переменные, которые приравниваются к нулю, называются небазисными переменными.

Действительно, приравнивая в системе уравнений (1.8) две переменные (n-m=2), например, х1 и х2, сразу получаем базисное решение S1=5; S2=8; S3=3; S4=2, которое соответствует вершине О.

Полученные результаты удобно представить в виде следующей симлекс-таблицы:


Базисные переменные

х1

х2

S1

S2

S3

S4

Решение

S1

1

1

1

0

0

0

5

S2

1

2

0

1

0

0

8

S3

1

0

0

0

1

0

3

S4

1

-1

0

0

0

1

2

^ L уравнение

-2

-3

0

0

0

0

0


Эта таблица сформирована следующим образом: в столбце базисные переменные записаны начальные базисные переменные, которые получились при приравнивании небазисных переменных х1 и х2 к нулю. В столбце решение приведены значение базисных переменных. В строках базисных переменных приведены коэффициенты уравнений (1.8), соответствующие своим переменным. В нижней строке стоят коэффициенты L-уравнения, взятые с противоположным знаком. Для начального базисного решения L=2*0+3*0=0, что и показано в правом нижнем углу таблицы.

После того, как получено начальное решение (определены координаты одной из вершин ОДР), необходимо определить, является ли полученное начальное решение оптимальным.

Анализируя L-уравнение, замечаем, что обе небазисные переменные х1 и х2, равные нулю, имеют отрицательные коэффициенты (в исходной целевой функции эти коэффициенты положительные). Так как мы решаем задачу максимизации целевой функции, то значение L может быть улучшено как при увеличении х1 ,так и х2. Таким образом полученное начальное решение не является оптимальным. Итак, дадим формулировку оптимальности решения.

Условие оптимальности. Если все коэффициенты при небазисных переменных в L уравнении в задаче максимизации (минимизации) целевой функции неотрицательны (не положительны), то полученное решение является оптимальным.

Если решение не оптимально, то необходимо перейти к соседней вершине ОДР, для чего одна базисная переменная должна стать небазисной (нулевой), а небазисная стать базисной.

Очевидно, что вводимой в базис переменной, должна быть та, которая в L-уравнении в задаче максимизации (минимизации) имеет наибольший отрицательный (положительный) коэффициент. В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно.

При этом изменение значения целевой функции наилучшее. Для определения, какую базисную переменную следует исключить из числа базисных (перевести в небазисную), используют условие допустимости.

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


2 . 5. МЕТОД БОЛЬШИХ ШТРАФОВ (М –метод)

Если в исходной задаче ЛП хотя бы одно ограничение имеет знак = или > , то сразу получить начальное допустимое решение не удается. Действительно , пусть требуется найти такие X1 и Х2 , которые обеспечивают max L = 2X1 + X2 при ограничениях



Х1 + 2Х2 = 6 ;

Х1 – Х2 > 2 ;

Х1 < 5 ;

Х1 , Х2. > 0 .


В стандартной форме эта задача имеет вид :

max L = 2Х1 + Х2 ;

Х1 + 2Х2 = 6 ;

Х1 – Х2 – Х3 = 2 ;

Х1 + Х4 = 5;

Х1 , Х2 , Х3 , Х4 > 0 .


Имеем три уравнения (m = 3) и четыре неизвестных n = 4. Это означает , что каждому базисному решению соответствует одна

( n – m = 1) небазисная ( равная нулю ) переменная . Приравняем , например , Х1 нулю , получаем Х4 = 5 ; Х2 = 3 ; Х3 = -5 , но это решение не является допустимым ( Х3 не является неотрицательной ).

Для простого получения начального допустимого решения разработан метод больших штрафов или М – метод. Суть его в следующем. В уравнения, которые в исходном виде были записаны со знаками >- и = вводят искусственные неотрицательные переменные R і.

Для рассматриваемого примера имеем:

min L = 3 Х 1 + Х 2 + MR 1 ;

5 Х 1 + 4 Х 2 –Х 3 + R 1 =25 ;

Х 1 + Х 4 = 3 ;

Х 1, Х 2, Х 3, Х 4, R 1 > 0 .


За использование этих переменных в составе целевой функции вводят штраф, используя большой положительный коэффициент М. На конечной стадии оптимизации переменные R i должны принять нулевое значение, при этом не будет их влияния на целевую функцию. Очевидно, что в задаче максимизации коэффициент М вводится в целевую функцию со знаком минус, а в задаче минимизации со знаком плюс. Это обусловит недопустимость положительных значений искусственных переменных в оптимальном решении.

После введения искусственных переменных легко получается начальное допустимое решение путём приравнивания к нулю n-m переменных . В рассматриваемом примере n – m = 5 – 2 = 3. Приравнивая нулю Х 1, Х 2 и Х 3 получаем R 1 = 25 и Х 4 = 3 .

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

В рассматриваемой примере


R 1 = 25 - 5 Х 1 – 4 Х 2 + Х 3 .


Тогда


L = 3 Х 1 + Х 2 + MR 1 = 3 Х 1 + Х 2 + М ( 25 – 5 Х 1 – 4 Х 2 +

Х 3 ) = ( 3 – 5 М ) Х 1 + ( 1- 4 М ) Х 2 +МХ 3 +25М.


Симплекс – таблица, соответсвующая начальному допустимому решению , имеет вид


БП

Х1

Х2

Х3


Х4

R1

Решение




R1

5

4

-1

0

1

25




Х4

1

0

0

1

0

3

Ведущая строка

L


-3+5М

-1+4М



0

0

25М







Ведущий столбец


Дальнейшая последовательность симплекс – таблиц , проводящих к оптимальному решению задачи , представлена ниже.


БП

Х1

Х2

Х3

Х4

R1

Решение



R1


0

4

-1

-5

1

10

Ведущая строка

Х1

1

0

0

1

0

3




L

0

-1+4М



3-5М

0

9+10М




























Х2

0

1

-1/4

-5/4

1/4

2,5




Х1

1

0

0

1

0

3




L

0

0

-1/4

7/4

¼-М

11,5






Оптимальное решение следующее : Х1 = 3; Х2 = 2,5 ;

min L = 11,5.


Недостаток М – метода связи с возможностью ошибок в вычислениях обусловленных очень большой величиной коэффициента М , которые происходят вследствие округления чисел при расчетах на цифровых ЭВМ.

Схожі:

2 Графический метод решения задач линейного программирования icon2 Графический метод решения задач линейного программирования
Графическое решение задач лп дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения...
2 Графический метод решения задач линейного программирования icon2 Графический метод решения задач линейного программирования
Графическое решение задач лп дает наглядное представление процесса нахождения оптимального решения, а также анализа полученного решения...
2 Графический метод решения задач линейного программирования iconКонтрольные вопросы по дисциплине «Исследование операций» Математическая модель задачи линейного программирования. Пример
Определение дефицитных и недефицитных ресурсов в задаче лп на основе ее графического решения. Пример
2 Графический метод решения задач линейного программирования iconКонтрольные вопросы по дисциплине «Исследование операций» Математическая модель задачи линейного программирования. Пример
Определение дефицитных и недефицитных ресурсов в задаче лп на основе ее графического решения. Пример
2 Графический метод решения задач линейного программирования iconПрактическая работа № Тема: Нахождение решений уравнений и систем уравнений
Цель: Освоить графический метод для решения уравнений и систем уравнений, научиться решать уравнения с одним неизвестным с помощью...
2 Графический метод решения задач линейного программирования icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существуют тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
2 Графический метод решения задач линейного программирования icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существует тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
2 Графический метод решения задач линейного программирования iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Графический метод решения задач линейного программирования iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Графический метод решения задач линейного программирования icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи