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

Рассмотренные выше примеры позволяют сформулировать общую задачу линейного программирования.

Общая форма записи модели задачи ЛП

Целевая функция (ЦФ)

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность.

Пропорциональность означает, что вклад каждой переменной в ЦФ и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной j x . Т.е. в разных ситуациях одна единица j-го товара будет приносить разный доход.

Аддитивность означает, что ЦФ и ограничения должны представлять собой сумму вкладов от различных переменных. Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.

Допустимое решение – это совокупность чисел (план) , удовлетворяющих ограничениям задачи (1.1).

Оптимальное решение – это план, при котором ЦФ принимает свое максимальное (минимальное) значение.

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

(1.3)

Очевидно, случай, когда линейную функцию нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

(1.4)

Основная задача линейного программирования не обязательно должна иметь решение. Может оказаться, что уравнения (1.1) противоречат друг другу или они имеют решение, но не в области неотрицательных значений Тогда ОЗ не имеет допустимых решений. Наконец, может оказаться, что допустимые решения 03 существуют, но среди них нет оптимального: функция Z в области допустимых решений не ограничена снизу.

Например.

Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски используется два исходных продукта A и B. Расходы продуктов A и B на 1 т. соответствующих красок и запасы этих продуктов на складе приведены в таблице 1:

Таблица 1 – Исходные данные

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

Составление математической модели задачи.

1) Переменные задачи.

x₁ – количество производимой краски для внутренних работ;

x₂ - соответствующее количество краски для наружных работ.

2)Ограничения, которым должны удовлетворять переменные задачи:

x₁ , x₂ 0;

по расходу продукта A: x₁ + 2x₂ 3;

по расходу продукта B: 3x₁ + x₂ 3.

3) Целевая функция задачи.

Обозначим Z доход от продажи краски (в у.е.), тогда целевая функция задачи записывается как:

max Z(х) = 2x₁ + x₂.

Таким образом, математическая модель выглядит следующим образом:

max Z = 2x₁+x₂.

ограничения:

.

Так как переменные задачи x₁ и x₂ входят в целевую функцию и ограничения задачи линейно, то соответствующая задача оптимизации называется задачей линейного программирования (ЗЛП).

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

1) Что является искомыми величинами задачи?

2) Какова цель решения? Какой параметр задачи служит критерием эффективности (оптимальности) решения, например, прибыль, себестоимость, время и т.д. В каком направлении должно изменяться значение этого параметра (к max или к min) для достижения наилучших результатов?

3) Какие условия в отношении искомых величин и ресурсов задачи должны быть выполнены? Эти условия устанавливают, как должны соотноситься друг с другом различные параметры задачи, например, количество ресурса, затраченного при производстве, и его запас на складе; количество выпускаемой продукции и емкость склада, где она будет храниться; количество выпускаемой продукции и рыночный спрос на эту продукцию и т.д.

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

1) Искомые величины являются переменными задачи, которые как правило обозначаются малыми латинскими буквами с индексами, например, однотипные переменные удобно представлять в виде ( )n 2 1 x ,..., x , x X = .

2) Цель решения записывается в виде целевой функции, обозначаемой, например, ( ) X L . Математическая формула ЦФ ( ) X L отражает способ расчета значений параметра – критерия эффективности задачи.

3) Условия, налагаемые на переменные и ресурсы задачи, записываются в виде системы равенств или неравенств, т.е. ограничений. Левые и правые части ограничений отражают способ получения (расчет или численные значения из условия задачи) значений тех параметров задачи, на которые были наложены соответствующие условия.