Методика выполнения работы
Примеры задач нелинейного программирования
Пример 4.1. Для транспортировки некоторого химиката требуется изготовить контейнеры.
Обозначим высоту контейнера как H, а размеры его основания (длину и ширину) – как L. Тогда для данной задачи можно построить следующую математическую модель:
H³1
H£3
H∙L2=6
Е = 6∙L2 + 24∙H∙L + 4∙L2 ® min
Здесь первое и второе ограничения устанавливают, что высота контейнера должна составлять от 1 до 3 м; третье ограничение устанавливает, что емкость контейнера равна 6 м3. Целевая функция Е выражает стоимость контейнера (первое слагаемое – стоимость материала для основания, второе – стоимость материала для стенок, третье – для крышки). Данная задача представляет собой задачу нелинейного программирования: нелинейными здесь являются целевая функция и ограничение на емкость контейнера.
Пример 4.2. Предприятие выпускает электроприборы двух типов (А и В) и запасные части к ним. В комплект запасных частей, выпускаемых вместе с каждым прибором, может входить от трех до шести запасных частей, причем количество запасных частей для всех приборов одного типа должно быть одинаковым. Расход материалов на выпуск приборов и запасных частей следующий.
Таблица 6.2
| Материал | Прибор А | Запасная часть к прибору А | Прибор В | Запасная часть к прибору В |
| Провод, см Пластмасса,г | 1,5 |
Предприятие имеет возможность израсходовать на выпуск приборов не более 0,6м провода и не более 0,5кг пластмассы.
Прибыль предприятия от выпуска одного прибора А составляет 8 ден.ед, одной запасной части к прибору А – 2 ден.ед., одного прибора В – 9 ден.ед, одной запасной части к прибору В – 1,5 ден.ед.
Требуется определить, сколько приборов каждого типа и запасных частей к ним должно выпустить предприятие, чтобы получить максимальную прибыль.
Введем переменные: x1 – количество приборов типа А; x2 – количество запасных частей к ним; x3 – количество запасных частей в комплекте к одному прибору типа А (соотношение количество запасных частей и приборов типа А); x4 – количество приборов типа В; x5 – количество запасных частей к ним; x6 – количество запасных частей в комплекте к одному прибору типа В (соотношение количество запасных частей и приборов типа В).
Составим математическую модель задачи:
x2 = x1 x3
x3£6
x3³3
x5 = Х4Х6
x6£6
x6³3
7 x1 + 3 x2 + 10 x4 + 2 x5 £ 60
12 x1 + 2 x2 + 8 x4 + 1,5 x5 £ 500
Хi – целые, i=1,…,6
Хi ³0, i=1,…,6
Е=8 x1+ 2 x2 + 9 x4 + 1,5 x5 ® max
Здесь первое ограничение устанавливает, что общее количество запасных частей к приборам А (x2) должно быть равно произведению количества этих приборов (x1) на количество запасных частей в одном комплекте (x3). Второе и третье ограничения устанавливают, что количество запасных частей к одному прибору типа А должно составлять не менее трех и не более шести. Четвертое, пятое и шестое ограничения имеют тот же смысл, но для приборов типа В. Седьмое и восьмое ограничения устанавливают предельный расход провода и пластмассы. Целевая функция выражает прибыль от выпуска приборов и запасных частей. В этой задаче нелинейными являются первое и четвертое ограничения.
Пример 4.3. Предприятие выпускает электронные изделия двух типов (изделия А и В). На выпуск изделий расходуется платина и палладий. На одно изделие А требуется 13г платины и 8г палладия, на одно изделие В – 6г платины и 11г палладия. Предприятие имеет возможность использовать не более 90г платины и не более 88г палладия.
Изделия А продаются по цене 12 тыс. ден.ед., изделия В – по 10 тыс. ден.ед.
Величины себестоимости изделий (т.е. затраты на их выпуск) зависят от объема их производства и приближенно описываются следующими формулами:
· себестоимость одного изделия А: 7 + 0,2 x1, где x1 – объем производства изделий А;
· себестоимость одного изделия В: 8 + 0,2 x2, где x2 – объем производства изделий В;
Требуется составить план производства, обеспечивающий предприятию максимальную прибыль.
Как отмечено выше, объемы производства изделий А и В обозначены через переменные x1 и x2. Составим целевую функцию задачи, выражающую прибыль от производства изделий. Будем считать, что прибыль от продажи одного изделия представляет собой разность его цены и себестоимости.
Прибыль от продажи одного изделия А можно выразить следующей формулой: 12 – (7 + 0,2 x1) = 5 – 0,2 x1. Аналогично выразим прибыль от рподажи одного изделия В: 10 – (8 + 0,2 x2) = 2 – 0,2 x2. Таким образом, целевая функции задачи (прибыль от продажи всех изделий А и В) имеет следующий вид:
Е = (5 – 0,2 x1) x1 + (2 – 0,2 x2) x2 = 5 x1 – 0,2 x12 + 2 x2 – 0,2 x22 ® max.
Приведем полную математическую модель задачи:
13 x1 + 6 x2 £ 90
8 x1 + 11 x2 £ 88
x1, x2³ 0
x1, x2 – целые
Е = 5 x1 – 0,2 x12 + 2 x2 – 0,2 x22 ® max.
Здесь ограничения устанавливают предельный расход платины и палладия.
В этой задаче система ограничений линейная, а целевая функция – нелинейная (квадратичная). Таким образом, данная задача представляет собой задачу нелинейного квадратичного программирования.