Зенкевич Н.А. Практикум по исследованию операций

Подождите немного. Документ загружается.

1.2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 11

1.2.2 Пример формализации задачи ЛП

Напишем математическую постановку следующей задачи:

Завод про производству строительных смесей изготовляет два вида продукции: строи-

тельные смеси для наружных работ (Тип 1) и строительные смеси для внутренних работ

(Тип 2). Для производства строительных смесей используются два типа ресурсов гипс

A и цемент B. Максимально возможные суточные запасы этих ресурсов составляют 12

и 6 т., соответственно. В таблице даны расходы гипса и цемента на 1т. соответствующих

строительных смесей.

Исходный Расход ресурсов (в тоннах) Суточный запас

продукт на тонну строительной смеси (в тоннах)

производства Тип 1 Тип 2

Гипс A 3 2 12

Цемент B 1 2 6

Суточный спрос на строительную смесь второго типа никогда не превышает спроса

на на строительную смесь первого типа более чем на 1т. Кроме того, спрос на на строи-

тельную смесь второго типа никогда не превышает 2т. в сутки. Продукция обоих видов

поступает в оптовую продажу. Известны оптовые цены одной тонны строительной сме-

си: 1000 руб. для строительной смеси первого типа, 3000 руб. для строительной смеси

второго типа. Какое количество строительной смеси каждого типа должна производить

фирма, чтобы доход от реализации продукции был максимальным?

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

Для решения задачи необходимо построить математическую модель. Процесс построения

модели можно разбить на несколько частей.

• Определим, какие величины необходимо определить в модели (каковы переменные

модели).

• Определим цель оптимизации.

• Определим каким ограничениям должны удовлетворять переме нные.

Определение переменных – первый шаг в создании модели. После определения пере-

менных построение ограничений и целевой функции обычно не составляет трудностей.

12 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

В нашем примере необходимо определить суточные объемы производства смесей для

наружных и внутренних работ (смеси первого и второго типов). Обозначим эти объемы

как переменные модели:

(в тоннах) – ежедневный объем производства строительной смеси первого типа

(для наружных работ).

(в тоннах) – ежедневный объем производства строительной смеси второго типа

(для внутренних работ).

Используя эти переменные строим целевую функцию, как суммарный ежедневный

доход. Обозначим целевую функцию через z (в тыс. руб.) и положим z = 1x

+3x

, тогда

в соответствии с целями компании получаем:

max z = max(1x

+ 3x

Из вида выражения для z следует, что целевая функция, будет возрастать при уве-

личении ежедневных объемов производства смесей.

Перейдем к ограничениям, которым должны удовлетворять переменные модели x

, x

Ограничения на сырье могут быть записаны следующим образом:







Используемый объем

ресурсов для производства

обоих видов смесей







≤





Максимально возможный

суточный запас ресурсов





Из таблицы с данными получаем следующее.

• ограничения на расход ресурсов

+ 2x

≤ 12; (гипс А) (1)

+ 2x

≤ 6; (цемент В) (2)

• ограничения на спрос

−x

+ x

≤ 1; (спрос 1) (3)

≤ 2; (спрос 2) (4)

• объем производства ни одного из видов продукции не может быть отрицательным,

поэтому:

≥ 0; (5)

≥ 0; (6)

1.2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 13

Окончательно искомая задача ЛП может быть записана следующим образом:

max z = max(x

+ 3x

);

+ 2x

≤ 12,

+ 2x

≤ 6,

−x

+ x

≤ 1,

≤ 2,

≥ 0, x

≥ 0;

1.2.4 Геометрический (графический) способ решения задачи ли-

нейного программирования

Полезный метод для решения задачи ЛП заключается в геометрическом изображении

множества допустимых решений и нахождении оптимального решения. Следует отме-

тить однако, что такой метод применим только для задач малой размерности (количе-

ство свободных переменных 2 или 3). Практически его применяют только для случая

2-х переменных.

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

ния (при максимизации)

• Записать каждое ограничение задачи ЛП как равенство (уравнение) и нарисовать

соответствующую прямую в координатной плоскости (координатном пространстве,

если случай трехмерный);

• Для каждого ограничения (неравенства) определить (нарисовать) допустимую об-

ласть, а затем допустимую область для всех ограничений. Оно представляет собой

пересечение таких областей для всех ограничений. Полученная область представ-

ляет собой множество допустимых решений задачи ЛП;

• Записать целевую функцию для произвольного уровня прибыли;

• Сдвигать линию уровня целевой функции в направлении возрастания прибыли;

• Экстремальная (угловая) точка, которая лежит в пересечении опорной прямой и

множества допустимых решений и будет оптимальным решением;

14 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

• Определить уравнения, пересекающиеся в оптимальной крайней точке. Решить

данную систему уравнений и найти оптимальное решение. Вычислить значение

целевой функции в оптимальной точке (значение задачи ЛП).

1.2.5 Пример графического решения задачи

Используя модель построенную в предыдущем разделе.

max z = max(x

+ 3x

);

+ 2x

≤ 12, (1)

+ 2x

≤ 6, (2)

−x

+ x

≤ 1, (3)

≤ 2, (4)

≥ 0, (5)

≥ 0; (6)

Задача содержит только две переменные, поэтому ее можно решить графически. В

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

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

допустимых решений, в которой одновременно выполняются все ограничения модели.

Рассмотрим условия неотрицательности переменных: x

≥ 0 и x

≥ 0. Эти два усло-

вия показывают что множество допустимых решений будет находится в первом квад-

ранте.

Для того чтобы учесть оставшиеся ограничения, заменим неравенства на равенства

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

Рассмотрим первое ограничение 3x

+ 2x

≤ 12. Заменим его уравнением прямой

+ 2x

= 12. Чтобы провести эту прямую, надо найти две различные точки, лежащие

на этой прямой. Например, если x

= 0, то x

= 12/2 = 6. Аналогично для x

= 0,

находим x

= 12/3 = 4. Итак, наша прямая проходит через две точки (0,6) и (4, 0). Эта

прямая обозначена на рисунке рис.1.1.1 как прямая (1).

Рассмотрим, как графически интерпретируются неравенства. Каждая прямая делит

плоскость (x

, x

) на два полупространства. Точки полуплоскости, расположенные по

одну сторону прямой удовлетворяют неравенству, а точки, лежащие по другую, - нет.

Проверяем условия выполнения неравенства (1). Точки, лежащие ниже прямой (1), удо-

влетворяют неравенству 3x

+2x

≤ 12. (Подставив точку (0,0), получаем 0 ≤ 12). Анало-

1.2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 15

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

допустимые полупространства, в которых выполняются услов ия ограничений.

В результате получим пространство решений – заштрихованный многоугольник. Точ-

ки пространства допустимых решений, находящиеся внутри многоугольника и на его

границе, удовлетворяют одновременно всем ограничениям, поэтому решения соответ-

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

решений содержит бесконечное число точек, необходима процедура поиска оптимального

решения, отличная от прямого перебора.

1 2 3 4 5 6

(4)

µ´

¶³

(3)

µ´

¶³

¢®

(2)

µ´

¶³

´+

(1)

µ´

¶³

(6)

µ´

¶³

(5)

µ´

¶³

Рис.1.1.1 Пространство допустимых решений модели

Для того чтобы найти оптимальное решение определим в каком направлении воз-

растает целевая функция z = x

+ 3x

. Построим прямую x

+ 3x

= 0. Чтобы убе-

диться в каком направлении возрастает функция можно, например, построить прямую

+3x

= 12). Иначе можно определить направление возрастания целевой функции из ее

уравнения. Коэффициенты перед переменными x

, x

- это координаты нормали к пря-

мой, определяемой целевой функцией. Таким образом в нашем случае целевая функция

будет изменяться в направлении вектора (1, 3).

16 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Для нахождения оптимального решения, следует перемещать п рямую, соответству-

ющую целевой функции, в направлении возрастания до тех пор пока она не сместится

в область недопустимых решений. Оптимальным решением является точка пересечения

области допустимых решений и прямой соответствующей максимально возможному зна-

чению целевой функции.

В нашем примере оптимальным решением будет точка C, которая является точкой

пересечения прямых (1) и (2). Значения переменных x

, и x

в этой точке определяются

решением следующей системы двух уравнений:

+ 2x

= 12,

+ 2x

= 6.

Решая эту систему получаем оптимальный план выпуска смесей обоих типов: x

∗

2, x

∗

= 2, то есть суточный объем строительной смеси первого типа должен быть 2

т., строительной смеси второго типа – 2 т. Доход, получаемый в этом случае составит

∗

= 2 + 3 ∗ 2 = 8 тыс. руб.

1 2 3 4 5 6

(4)

µ´

¶³

(3)

µ´

¶³

¢®

(2)

µ´

¶³

´+

(1)

µ´

¶³

z = x

+ 3x

(6)

µ´

¶³

(5)

µ´

¶³

££±

(1;3)

Рис.1.1.2. Оптимальное решение модели

1.2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 17

1.2.6 Задачи для самостоятельного решения

Постройте математические модели ЛП и решите графически следующие за-

дачи:

1.2.1. Предприятие электронной промышленности выпускает 2 модели радиоприем-

ников, причем каждая модель производится на отдельной технологической линии. Су-

точный объем производства первой линии 60 изделий, второй линии 75 изделий. На

радиоприемник первой модели расходуется 10 однотипных элементов электронных схем,

на радиоприемник 2 модели – 8 таких же элементов. Максимальный суточный запас

используемых элементов равен 800 единицам. Прибыль от реализации одного прием-

ника первой и второй модели равны 30 и 20 соответственно. Определите оптимальные

суточные объемы производства первой и второй моделей.

1.2.2. Фабрика головных уборов производит два типа шляп. Производство шляпы

первого типа требует в два раза больше временных ресурсов, чем производство шляпы

второго типа. Если фабрика будет производить только шляпы второго типа, то в день

она может изготовить 400 таких шляп. Рынок накладывает ограничения на производство

шляп: не более 150 шляп первого типа и 200 шляп второго типа. Д оход от производства

шляп первого типа составляет 8 у.е. на единицу первого типа и 5 у.е. – второго типа.

Составьте оптимальный план производства, приносящий максимальный доход.

1.2.3. Компания производит два вида продукции A и B. Объем продаж продукта A

составляет не менее 80 процентов от общего объема продаж продуктов A и B. Вместе с

тем компания не может производить более 100 единиц продукта A в день. Для производ-

ства этих продуктов используется одно и тоже сырье, поступление которого ограничено

240 фунтами в день. На изготовление единицы продукта A расходуется 2 фунта сырья,

а единицы продукта B – 4 фунта. Цена одной единицы продуктов A и B составляет 20 и

50 у.е. соответственно. Сколько единиц продукции каждого типа нужно изготавливать,

чтобы доход был максимальным?

1.2.4. Факультет послевузовского обучения местного колледжа предлагает в общей

сложности до 30 курсов каждый семестр. Все курсы условно можно разбить на два

типа: практические, такие как деревообработка, обучение работе на компьютере и т.п.

и гуманитарные, например история, музыка и изобразительное искусство. Чтобы удо-

влетворить запросы обучающихся в каждом семестре должно предлагаться не менее 10

курсов каждого типа. Факультет оценивает доход от одного практического курса в 1500

18 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

у.е., а гуманитарного – в 1000. Какова оптимальная структур а курсов для факультета?

1.2.5. Завод бытовой химии производит два вида чистящих средств, A и B, используя

при этом сырье 1 и 2. Обработка одной единицы сырья 1 стоит 8 у.е., в результате про-

изводится 0.5 единицы средства A и столько же средства B. Обработка одной единицы

сырья 2 стоит 5 у.е., в результате получается 0.6 единицы сре дства A и 0.4 единицы

средства В. Ежедневное производство средства A должно быть не менее 10 и не более 15

единиц. Для средства B аналогичные ограничения составляют 12 и 20 единиц. Найдите

оптимальную структуру выпуска чистящих средств.

1.2.6. Студент Джек решил распределить свое дневное время (10 часов) между учебой

и игрой в баскетбол. Привлекательность игрового времени он оценивает в два раза вы-

ше, чем привлекательность времени, затраченного на учебу. Но имея совесть и чувство

долга. Джек решил, что время игры не должно превышать время учебы. Кроме того,

он заметил, что если выполнять все задания, на игру останется не более 4 часов в день.

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

удовольствие и от учебы, и от игры.

1.2.7. Компания имеет возможность рекламировать свою прод укцию по местному

радио и телевидению. Бюджет на рекламу ограничен суммой 10000 у.е. в месяц. Одна

минута рекламного времени на радио стоит 15 у.е., а на телевидении – 300 у.е. Ком-

пания предполагает, что реклама на радио по времени должна превышать рекламу на

телевидении не менее, чем в два раза. Вместе с тем известно, что нерационально исполь-

зовать более 400 минут рекламы на радио в месяц. Последние исследования показали,

что реклама на телевидении в 25 раз эффективнее рекламы на радио. Разработайте

оптимальный бюджет для рекламы на радио и телевидении.

Решите геометрически (или убедитесь в неразрешимости) следующих за-

дач ЛП:

1.2.8 1.2.9 1.2.10

min z = min(5x

− 3x

);

+ 2x

≥ 6,

− 3x

≥ −6,

− x

≤ 4,

+ 7x

≤ 28;

≥ 0, x

≥ 0.

max z = max(2x

+ x

);

− 2x

≥ 4

+ 2x

≥ 10,

− 3x

≤ 12,

+ 4x

≤ 28;

≥ 0, x

≥ 0.

max z = max(2x

+ 2x

);

− 2x

≥ −6,

+ x

≥ 3

≤ 3,

≤ 5;

≥ 0, x

≥ 0.

1.2. ФОРМАЛИЗАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 19

1.2.11 1.2.12 1.2.13

max z = max(2x

− 4x

);

− 5x

≤ 16,

+ 3x

≤ 2,

+ 7x

≥ 9;

≥ 0, x

≥ 0.

max z = max(3x

+ 3x

);

− 4x

≤ 4,

32x

+ 2x

≤ 6,

−x

+ x

≤ 1,

+ 2x

≥ 2;

≥ 0, x

≥ 0.

max z = max(2x

− x

);

− x

≥ −3

+ 7x

≤ 42,

− 3

≤ 6,

+ x

≥ 4;

≥ 0, x

≥ 0.

1.2.14 1.2.15

max z = max(x

− x

);

−x

+ x

≥ 8,

+ 5x

≤ 80,

− 2x

≤ 2,

+ 4x

≥ 4;

≥ 0, x

≥ 0.

min z = min(7x

− x

);

+ x

≥ 3,

+ x

≥ 5,

+ 5x

≥ 5;

0 ≤ x

≤ 4,

0 ≤ x

≤ 4.

20 Глава 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.3 Прямой симплекс-метод для задачи максимизации

Использование графического способа удобно только при решении задач ЛП с двумя пе-

ременными. Для большего числа переменных используется симплекс метод. Для того,

чтобы к задаче ЛП можно было применить симплекс-метод, она должна быть представ-

лена в канонической форме.

1.3.1 Эквивалентные преобразования

На практике общая задача линейного программирования должна быть приведена к од-

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

называются эквивалентные формулировки. Обычно используются следующие эквива-

лентные формулировки.

• min z = max(−z);

• x

≥≤ 0 ⇐⇒







= x

− x

−

≥ 0, x

−

≥ 0;

• x

≥≤ 0, j =

1, n ⇐⇒







= x

− x

≥ 0, j =

1, n, x

≥ 0;

• a

+ a

+ . . . + a

≤ b

, ⇐⇒ a

+ a

+ . . . + a

+ s

= b

, s

≥ 0, i =

1, m;

• a

+. . . +a

≥ b

, ⇐⇒ a

+. . . +a

−s

= b

, s

≥ 0, i = 1, m;

• a

+ a

+ . . . + a

= b

, ⇐⇒







+ a

+ . . . + a

≤ b

+ a

+ . . . + a

≥ b

;

• a

+. . .+a

= b

, i =

1, m ⇐⇒







+ a

+ . . . + a

≤ b

, i =

1, m,

i=1

+ a

+ . . . + a

− b

) ≥ 0,

⇐⇒







+ a

+ . . . + a

≥ b

, i =

1, m,

i=1

+ a

+ . . . + a

− b

) ≤ 0;