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

Лекция 14-15

Вступление.

Сущность ЛП состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений. Т.о. ЛП – это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. При этом целевые функции и ограничения строго линейны.

Следует с самого начала предупредить: предпосылка линейности, когда в реальности подавляющее большинство зависимостей носит более сложный нелинейный характер, есть огрубление, упрощение действительности. В некоторых случаях оно достаточно реалистично, в других же выводы, получаемые с помощью решения задачи ЛП, оказываются весьма несовершенными.

Математическая модель любой задачи ЛП включает в себя:

- переменные, которые следует определить;

- целевую функцию, подлежащую оптимизации;

- систему ограничений в форме линейных уравнений и неравенств.

Пример:

Фирма производит типографскую краску двух цветов: черную и синюю из сырья двух типов М1 и М2.

	Расход сырья (в тоннах) на тонну краски	Максимально возможный ежедневный расход сырья
Черная	Синяя
Сырье М1
Сырье М2
Доход (в 1000$) на тонну краски

Отдел маркетинга фирмы ограничил ежедневное производство синей краски до 2 т. (из-за отсутствия спроса), а также поставил условие, чтобы ежедневное производство синей краски не превышало более чем на тонну аналогичный показатель производства черной краски. Фирме требуется определить оптимальное (наилучшее) соотношение между видами выпускаемой продукции для максимизации общего ежедневного дохода.

Математическая модель

х₁ – ежедневный объем производства черной краски;

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

Ежедневный расход сырья М1 и М2 ограничен соответственно 24 и 6 тоннами, поэтому получаем следующие ограничения:

Записываем ограничения по спросу: 1) х₂≤ 2; 2) разность между ежедневными объемами производства красок черного и синего цветов не должна превышать 1 тонну, т.е. х₂ – х₁ ≤ 1.

Еще одно неявное ограничение состоит в том, что переменные х₁и х₂ должны быть неотрицательными. Т.о. имеем:

Любое решение, удовлетворяющее ограничениям модели, является допустимым. Например, решение х₁ = 3 и х₂ = 1 будет допустимым, так как не нарушает ни одного ограничения, включая условие неотрицательности. Значение целевой функции при этом решении будет равно z = 5*3 + 4*1 = 19 (тыс. $).

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