5.2. линейное, целочисленное и нелинейное программирование

5.2. линейное, целочисленное и нелинейное программирование

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

п

экстремум функции Ц = 2^аіхі ~~^ extr ПРИ наличии следующих ог7=1

раничений:

п

2ZbjjXj<Cj, J = ...к; Xj>0 V/.

7=1

Имеется 150 л жидкости А и 150 л жидкости Б. Для получения одной бутыли смеси 1 нужно взять 2 л жидкости А и 1 л жидкости Б, а для получения одной бутыли смеси 2 нужно взять соответственно 1 л жидкости А и 4 жидкости Б.Смесь 1 продаётся по цене 2 ден. единицы, а смесь 2 3 ден. единицы за одну бутыль. Сколько нужно приготовить бутылей каждой смеси, чтобы общая их стоимость была наибольшей, при условии, что число бутылей со смесью 2 не менее числа бутылей со смесью 1?

Введём следующие обозначения: х {количество бутылей первой смеси; х 2 количество бутылей второй смеси. Стоимость бутылей первой смеси составляет 2х{ ден. единиц, а второй смеси 3х 2

ден. единиц, т. е. необходимо максимизировать целевую функцию (общую стоимость):

f( X) =2jc1 + 3jc2— max.

Помимо указанной функции мы имеем ряд ограничений.

е ограничение: можно потратить не более 150 л жидкости А:

2хх + х2 < 150

е ограничение: можно потратить не более 150 л жидкости В:

хх +4х2 < 150

е ограничение: число бутылей со смесью 2 не менее числа бутылей со смесью 1 :

Xi х2 < 0

е ограничение: количество бутылей не может быть отрицательным:

х > 0, х2 ^ 0 Таким образом, получаем следующую задачу: f( X) =2jc1 + 3jc2— max при условиях

2 xx+ 150 x1 +4x2 <150 хі~ х2<0 Хі> 0, X2 > 0

К аналогичным задачам приводятся транспортные задачи. Они имеют, как правило, следующую формулировку.

Имеется n поставщиков и m потребителей. Каждый поставщик имеет запасы некоторого товара в объеме ai, i=1...n, а каждому потребителю необходимо получить этого товара в объеме bj, j=1...m. Затраты на доставку одной единицы товара от поставщика № i к потребителю № j равны Cj. Разработать план доставки товаров, минимизирующий издержки.

Математическая формулировка этой задачи следующая: n m

i=1J=1

m

j=1 n

1

x jj> 0 Vi, j

Если общие запасы у поставщиков меньше, чем суммарные потребности, то второе равенство заменяется на неравенство (<bj). Если запасы превосходят потребности, то первое равенство заменяется на неравенство (<яг-).

Задачи такого типа решаются при помощи дисциплины, называемой «линейное программирование».

Иногда возникает задача с целочисленными переменными, например, когда необходимо распределить людей по объектам (невозможно поставить за прилавок 0,5 продавца или направить 1,3 курьера).

Такая задача является предметом рассмотрения разделом линейного программирования «целочисленное программирование».

И, наконец, возможны ситуации, когда либо целевая функция, либо ограничения, либо и то и другое вместе являются нелинейными. Эта задача предмет дисциплины «нелинейное программирование». В частности, к таким задачам относятся задачи формирования портфеля ценных бумаг.