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

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

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

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

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

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

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

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

Волгоград

УДК 519.85(07)

Г 78

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

технический

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

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

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

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

. (1)

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

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

x₂

x₁

x₂

x₁

а) ОДР – выпуклый многоугольник

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

x₁

x₂

x₁

x₂

в) ОДР – единственная точка

г) ОДР – прямая линия

x₁

x₂

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

Рис. 1.

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

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

Z = с₁х₁+ с₂x₂. Пусть область допустимых решений задачи – линейного программирования непустое множество (например, многоугольник А₁А₂А₃А₄А₅А₆, изображенный на рис. 2).

Рис. 2.

Выберем произвольное значение целевой функции Z = Z₀. Получим с₁х₁ +с₂x₂= Z₀, – это уравнение прямой линии. В точках прямой NM целевая функция сохраняет одно и то же постоянное значение Z₀. Считая в равенстве Z = c₁x₁+ c₂x₂Z – параметром, получим уравнение семейства параллельных прямых, которые называются линиями уровня целевой функции. Чтобы установить направление возрастания (убывания) целевой функции, найдем градиент этой функции:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

а) б)

в) г)

д) е)

Рис. 3.

Пример 1.

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

Таблица 1

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

Решение

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

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

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

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

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

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

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

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

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

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

l₃: 45x₁+ 30x₂= 4500000 – прямая, проходящая через точки (100000:0). (0:150000).

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

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

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

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

х₁^* = 46667, х₂^*= 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 погрузчик	10т 8р х₁₁	I0т 7р х₁₂
2 погрузчик	13т 12р х₂₁	13т 13р х₂₂
задание

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

Целевая функция minZ = 8x₁₁+ 7x₁₂+ 12х_{2 1}+ 13х₂₂

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

;

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

x₁₁+ х₂₁= 230;

х₁₂+ х₂₂= 168;

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

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

х₂₁= 230 - х₁₁;

х₂₂= 168 - х₁₂.

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

min Z = 4944 - 4x₁₁- 6x₁₂,

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

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

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

l₃: x₁₂= 168;

l₄: x₁₁= 230.

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

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

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

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

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

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

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