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

Раздел: Теория оптимизации.

Пусть - система линейных ограничений (т.е. система линейных уравнений или нестрогих линейных неравенств) с переменными , а - целевая функция вида . Задача линейного программирования формулируется следующим образом: найти при условиях . Обычно включает в себя условия неотрицательности всех переменных: - это вытекает из реального смысла чисел .

Различают две формы задач линейного программирования:

- каноническую форму, когда система ограничений состоит только из уравнений и условий неотрицательности (транспортная задача);

- стандартную форму, когда система состоит только из неравенств.

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

Процесс построения математической модели конкретной задачи линейного программирования включает в себя три основных этапа:

1) выбор переменных;

2) построение целевой функции;

3) учет ограничений, налагаемых на переменные.

Пример 1. Задача о банке.

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

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

Другое дело ценные бумаги, которые всегда можно продать. Поэтому существует правило, согласно которому коммерческие банки должны покупать в определенной пропорции ликвидные активы – ценные бумаги, чтобы компенсировать неликвидность кредитов. В нашем примере ликвидное ограничение таково: ценные бумаги должны составлять не менее 30% средств, размещенных в кредитах и ценных бумагах.

Пусть - средства, размещенные в кредитах, - средства, вложенные в ценные бумаги. Имеем следующую систему линейных ограничений:

1)

2)

3)

4) .

Цель банка состоит в том, чтобы получить максимальную прибыль от кредитов и ценных бумаг: , где - доходность кредитов, а - доходность ценных бумаг.

Пример 2. Задача о использовании ресурсов.

Предприятие имеет в своем распоряжении определенное количество ресурсов разного рода: рабочую силу, производственные ресурсы, площади и т.п. Допустим ресурсы трех видов , имеются в количествах условных единиц. Предприятие выпускает два вида товаров . Количество единиц каждого ресурса, требуемое для производства каждого товара приведено в таблице:

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

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

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

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

и максимизирующих функцию .

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

Пример 2. Графическое решение задачи о банке:

1)

2)

3)

4) .

Построим в плоскости полуплоскости заданные неравенствами 1)-4) – область допустимых решений. Для этого заменим неравенства равенствами и определим для каждого ограничения допустимую полуплоскость. Построим вектор и прямую уровня, перпендикулярную вектору и проходящую через начало координат. Перемещая эту прямую параллельно в направлении вектора , найдем последнюю точку пересечения прямой уровня и допустимого множества решений. (см. рисунок 1)

Найденная точка максимума находится на пересечении прямых 1 и 3. Ее координаты получаются решением следующей системы линейных уравнений:

Оптимальный портфель активов (максимум прибыли) имеет структуру . Максимальная прибыль составит

Рис. 1