Методика выполнения работы

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

Пример 4.1. Для транспортировки некоторого химиката требуется изготовить контейнеры.

Обозначим высоту контейнера как H, а размеры его основания (длину и ширину) – как L. Тогда для данной задачи можно построить следующую математическую модель:

H³1

H£3

H∙L²=6

Е = 6∙L² + 24∙H∙L + 4∙L² ® min

 

Здесь первое и второе ограничения устанавливают, что высота контейнера должна составлять от 1 до 3 м; третье ограничение устанавливает, что емкость контейнера равна 6 м³. Целевая функция Е выражает стоимость контейнера (первое слагаемое – стоимость материала для основания, второе – стоимость материала для стенок, третье – для крышки). Данная задача представляет собой задачу нелинейного программирования: нелинейными здесь являются целевая функция и ограничение на емкость контейнера.

Пример 4.2. Предприятие выпускает электроприборы двух типов (А и В) и запасные части к ним. В комплект запасных частей, выпускаемых вместе с каждым прибором, может входить от трех до шести запасных частей, причем количество запасных частей для всех приборов одного типа должно быть одинаковым. Расход материалов на выпуск приборов и запасных частей следующий.

Таблица 6.2

Материал	Прибор А	Запасная часть к прибору А	Прибор В	Запасная часть к прибору В
Провод, см Пластмасса,г				1,5

 

Предприятие имеет возможность израсходовать на выпуск приборов не более 0,6м провода и не более 0,5кг пластмассы.

Прибыль предприятия от выпуска одного прибора А составляет 8 ден.ед, одной запасной части к прибору А – 2 ден.ед., одного прибора В – 9 ден.ед, одной запасной части к прибору В – 1,5 ден.ед.

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

Введем переменные: x₁ – количество приборов типа А; x₂ – количество запасных частей к ним; x₃ – количество запасных частей в комплекте к одному прибору типа А (соотношение количество запасных частей и приборов типа А); x₄ – количество приборов типа В; x₅ – количество запасных частей к ним; x₆ – количество запасных частей в комплекте к одному прибору типа В (соотношение количество запасных частей и приборов типа В).

Составим математическую модель задачи:

 

x₂ = x₁ x₃

x₃£6

x₃³3

x₅ = Х₄Х₆

x₆£6

x₆³3

7 x₁ + 3 x₂ + 10 x₄ + 2 x₅ £ 60

12 x₁ + 2 x₂ + 8 x₄ + 1,5 x₅ £ 500

Х i – целые, i =1,…,6

Х i ³0, i =1,…,6

Е=8 x₁+ 2 x₂ + 9 x₄ + 1,5 x₅ ® max

 

Здесь первое ограничение устанавливает, что общее количество запасных частей к приборам А (x₂) должно быть равно произведению количества этих приборов (x₁) на количество запасных частей в одном комплекте (x₃). Второе и третье ограничения устанавливают, что количество запасных частей к одному прибору типа А должно составлять не менее трех и не более шести. Четвертое, пятое и шестое ограничения имеют тот же смысл, но для приборов типа В. Седьмое и восьмое ограничения устанавливают предельный расход провода и пластмассы. Целевая функция выражает прибыль от выпуска приборов и запасных частей. В этой задаче нелинейными являются первое и четвертое ограничения.

Пример 4.3. Предприятие выпускает электронные изделия двух типов (изделия А и В). На выпуск изделий расходуется платина и палладий. На одно изделие А требуется 13г платины и 8г палладия, на одно изделие В – 6г платины и 11г палладия. Предприятие имеет возможность использовать не более 90г платины и не более 88г палладия.

Изделия А продаются по цене 12 тыс. ден.ед., изделия В – по 10 тыс. ден.ед.

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

· себестоимость одного изделия А: 7 + 0,2 x₁, где x₁ – объем производства изделий А;

· себестоимость одного изделия В: 8 + 0,2 x₂, где x₂ – объем производства изделий В;

Требуется составить план производства, обеспечивающий предприятию максимальную прибыль.

Как отмечено выше, объемы производства изделий А и В обозначены через переменные x₁ и x₂. Составим целевую функцию задачи, выражающую прибыль от производства изделий. Будем считать, что прибыль от продажи одного изделия представляет собой разность его цены и себестоимости.

Прибыль от продажи одного изделия А можно выразить следующей формулой: 12 – (7 + 0,2 x₁) = 5 – 0,2 x₁. Аналогично выразим прибыль от рподажи одного изделия В: 10 – (8 + 0,2 x₂) = 2 – 0,2 x₂. Таким образом, целевая функции задачи (прибыль от продажи всех изделий А и В) имеет следующий вид:

Е = (5 – 0,2 x₁) x₁ + (2 – 0,2 x₂) x₂ = 5 x₁ – 0,2 x₁² + 2 x₂ – 0,2 x₂² ® max.

Приведем полную математическую модель задачи:

 

13 x₁ + 6 x₂ £ 90

8 x₁ + 11 x₂ £ 88

x₁, x₂³ 0

x₁, x₂ – целые

 

Е = 5 x₁ – 0,2 x₁² + 2 x₂ – 0,2 x₂² ® max.

 

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

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