Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Составители: Светлана Васильевна Мягкова, Елена Васильевна Морозова

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ВОЛГОГРАДСКОГО ГОСУДАРСТВЕННОГО ТЕХНИЧЕСКОГО УНИВЕРСИТЕТА

КАФЕДРА «ВЫСШАЯ МАТЕМАТИКА»

 

 

Графическое решение

задачи линейного программирования

 

Методические указания и индивидуальные задания

 

 

Волгоград

 

УДК 519.85(07)

Г 78

 

Графическое решение задачи линейного программирования: методические указания и индивидуальные задания / Сост. С. В. Мягкова, Е. В. Морозова; Волгоград. гос. техн. ун-т. – Волгоград, 2009. – 14 с.

 

Излагаются рекомендации графического решения задачи линейного программирования. Содержатся 60 вариантов заданий для самостоятельного решения.

Предназначены для студентов экономических специальностей.

 

Ил. 5. Табл. 2. Библиогр.: 2 назв.

 

Рецензент: Л. А. Крапивина

 

Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

 

Составители: Светлана Васильевна Мягкова, Елена Васильевна Морозова

 

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

Методические указания и индивидуальные задания

Под редакцией авторов

Темплан 2009 г., поз. № 36К.

Подписано в печать 28. 05. 2009 г. Формат 60×84 1/16.

Бумага листовая. Печать офсетная.

Усл. печ. л. 0,88. Усл. авт. л. 0,75.

Тираж 50 экз. Заказ №

Волгоградский государственный технический университет

400131 Волгоград, просп. им. В. И. Ленина, 28.

РПК «Политехник»

Волгоградского государственного технического университета

400131 Волгоград, ул. Советская, 35.

 

© Волгоградский

государственный

технический

университет, 2009

I. Область применения

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

Пусть задача линейного программирования задана в двумерном пространстве, т.е. ограничения содержат две переменные. Найти максимальное значение функции z = c1x1 + c2х2 при следующих ограничениях:

. (1)

Дадим геометрическую интерпретацию элементов этой задачи.

1. Каждоеиз ограничений (1) Задает на плоскости x1Ox2 некоторую полуплоскость. Их пересечение является областью допустимых решений задачи.

x2
x1
 

x2
 
x1

а) ОДР – выпуклый многоугольник б) ОДР – неограниченная выпуклая многоугольная область
 
x1
x2

x1
x2
 

в) ОДР – единственная точка г) ОДР – прямая линия

x1
 
x2

д) ОДР – пустое множество

Рис. 1.

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

2. Перейдем к геометрической интерпретации целевой – функции

Z = с1х1 + с2x2. Пусть область допустимых решений задачи – линейного программирования непустое множество (например, многоугольник А1 А2 А3 А4 А5 А6, изображенный на рис. 2).

 

Рис. 2.

Выберем произвольное значение целевой функции Z = Z0. Получим с1х12x2 = Z0, – это уравнение прямой линии. В точках прямой NM целевая функция сохраняет одно и то же постоянное значение Z0. Считая в равенстве Z = c1x1 + c2x2Z – параметром, получим уравнение семейства параллельных прямых, которые называются линиями уровня целевой функции. Чтобы установить направление возрастания (убывания) целевой функции, найдем градиент этой функции:

Вектор – указывает направление наискорейшего возрастания целевой функции, (антиградиент) – направление наискорейшего убывания.

Вектор перпендикулярен к прямым Z = const.

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

1. С учетом системы ограничений построить область допустимых решений (ОДР).

2. Построить вектор - вектор наискорейшего возрастания целевой функции.

3. Построить произвольную линию уровня Z = Z0. Перпендикулярную к вектору с внутри ОДР.

4. При решении задачи на максимум переместить линию уровня Z = Z0 в направлении так, чтобы она касалась области допустимых решений в ее крайнем положении (на рис. 2 – до точки А4). В случае решения задачи на минимум линию уровня Z = Z0 перемещают в антиградиентном направлении (на рис. 2 – до точки А1).

5. Определить оптимальный план х* = (х1*; х2*) и экстремальное значение целевой функции Z* = z(x*).

Как видно из рис. 3, возможны следующие случаи:

1) Оптимальный план единственный; линия уровня и область допустимых решений в разрешающем положении имеют одну общую точку (а).

2) Оптимальных планов бесконечное множество: в разрешающем положении линия уровня проходит через сторону области допустимых решений (б).

3) Целевая функция неограничена: линия уровня не может занять разрешающего положения (в, г).

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

5) Задача не имеет решений, так как область допустимых решений – пустое множество (е)

а) б)

в) г)

д) е)

Рис. 3.

Пример 1.

На фабрике планируется выпустить миткаль двух артикулов: № 30 и № 21 из одинаковой пряжи на одинаковых станках. Планируемый суммарный выпуск 80000 тыс. м. Известно, что в 1997 г. фабрика может выделить не более 8400 т основной пряжи и 4500 т уточной. Требуется составить такую производственную программу, при которой был бы перевыполнен запланированный выпуск ткани и суммарный выпуск ткани оказался бы максимальным (табл. 1).

Таблица 1

Ассортимент суровья расход пряхи на 1 тыс. м ткани, кг
основной уточной
миткаль № 30 миткаль № 21    

Решение

Пусть х1 (тыс. м) – выпуск миткаля № 30.

х2 (тыс. м) – выпуск миткаля № 21,

значит Х = (x12) – план задачи, тогда модель задачи будет следующая:

max Z = х1 + x2 при ограничениях x1 + х2 > 80000 (выпуск ткани должен быть перевыполнен);

60x1 + 70х2 8400000 (фабрика может выделить основной пряжи не более 8400 т);

45х1 + 30х2 4500000 (уточной пряжи может быть выделено не более 4500 т);

х1 0, х2 0 (условие не отрицательности переменных). Итак, целевая функция Z = x1 + х2 ограничения:

1. Построим область допустимых решений:

l1: х1 + х2 = 80000 – прямая, проходящая через точки (80000;0) (0:80000);

l2: 60x1 + 70x2 = 8400000 – прямая, проходящая через точки (0:120000). (140000:0):

l3: 45x1 + 30x2 = 4500000 – прямая, проходящая через точки (100000:0). (0:150000).

2. Построим вектор (1;1).

3. Построим линию уровня z = z0, перпендикулярную . Параллельным перемещением прямой Z = Z0 находим точку А, в которой целевая функция достигает максимума.

4. Решая совместно уравнения граничных прямых l2 и l3:

,

находим координаты точки А:

х1* = 46667, х2* = 80000, при этом Z* = max Z = Z(A) = 126667.

Итак, по оптимальному плану следует выпускать 46667 тыс. м миткаля < 30 и 80000 тыс. м миткаля № 21; тогда общий выпуск ткани 126667 тыс. м на 46667 тыс. м больше запланированного выпуска ткани.

3. Пример 2.

Двум погрузчикам разной мощности за 24 часа нужно погрузить на первой площадке 230 т, на второй – 68 т. Первый погрузчик на 1-ой площадке может погрузить 10 т в час. на 2-ой – 12 т. Второй погрузчик на каждой площадке может погрузить по 13 т в час. Стоимость работ, связанных с погрузкой 1 т первым погрузчиком на первой площадке 8 руб., на второй – 7 руб., вторым погрузчиком на первой площадке – 12 руб., на второй – 13руб. Нужно найти, какой объем работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной.

Решение

Пусть хij – объем работ (тоннах) i -го погрузчика (i = l,2) на j -ой площадке, (j = 1,2).

Условия задачи занесём в табл. 2.

Таблица 2

f t П1 П2 Лимит рабочего времени
1 погрузчик 10т 8р х11 I0т 7р х12  
2 погрузчик 13т 12р х21 13т 13р х22  
задание      

 

Построим математическую модель задачи.

Целевая функция minZ = 8x11 + 7x12 + 12х2 1+ 13х22

Ограничения на лимиты рабочего времени:

;

на необходимость выполнить задание:

x11 + х21 = 230;

х12 + х22 = 168;

условие не отрицательности: (i, j = 1,2). Итак, система ограничений будет:

Решим эту задачу графически. Для этого исключим из модели переменные х21 и х22, Из ограничений равенств имеем:

х21 = 230 - х11;

х22 = 168 - х12.

Подставив выражения для х21 и х22 в ограничения – неравенства и целевую функцию, получим задачу линейного программирования с двумя переменными х11 и х12:

min Z = 4944 - 4x11- 6x12,

 

.

1. Построим область допустимых решений:

l1: 11 + 5х12 = 1440 – прямая, проходящая через точки (0; 288), (240; 0);

l2: х11 + х12 = 86 – прямая, проходящая через точки (0;86), (86:0);

l3: x12 = 168;

l4: x11 = 230.

2. Построим градиент целевой функции (-4;-6).

3. Построим линию уровня Z = Z0, перпендикулярную .

4. Параллельно перемещая прямую Z = Z0 в антиградиентном направлении, найдем точку А, в которой целевая функция достигает минимума.

 

Функция Z достигает наименьшего значения при х11* = 100, х12* = 168; из выражений для х21 и х22 получим: х21* = 130, х22* = 0; min Z = 4944 – 4 × 100 - 6× 168 = 3536 руб.

Итак, по оптимальному плану первый погрузчик должен погрузить 100 т на первой площадке и 168 т – на второй; второму погрузчику надлежит погрузить 130 т на первой площадке.

4. Выполнить следующие задания.

Задача 1. Решите графическим методом задачу линейного программирования (x1 ≥ 0, x2 ≥ 0):

 

1. 6. 11.
2. 7. 12.
3. 8. 13.
4. 9. 14.
5. 10. 15.

 

16. 21. 26.
17. 22. 27.
18. 23. 28.
19. 24. 29.
20. 25. 30.

Задача 2. Найти графическим методом оптимальный план задач линейного программирования j ³ 0).

1. 8.
2. 9.
3. 10.
4. 11.
5. 12.
6. 13.
7. 14.

 

15. 23.
16. 24.
17. 25.
18. 26.
19. 27.
  28.
  29.
22. 30.

Список рекомендуемой литературы

1. Кузнецов Ю. Н. и др. Математическое программирование. –МЛ"Высшая школа", 1980.

2. Кузнецов А. В. Математическое программирование. – Минск, "Вышейшая школа", 1994.

 

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...