Линейные функции

Заметьте, что в данной модели все функции ограничений, а также целевая функция являются линейными функциями двух переменных решения. График линейной функции двух переменных представляет собой прямую линию. В общем случае линейная функция — это такая функция, в которую каждая переменная вместе со своим коэффи­циентом входит в виде отдельного члена (т.е. переменные не умножаются, не делятся друг на друга, не возводятся в степень (отличную от 1), нет логарифмических, экспонен­циальных или тригонометрических выражений и т.д.). Примером нелинейной функции может служить функция 14C+ 12CМ, поскольку слагаемое 12СМ содержит произведение переменных. Функция 9С^2 + 8М также является нелинейной, так как переменная С вoзводится во вторую степень. Другой пример нелинейной функции: 19LogC+ 12СМ. Примерами функций Excel, которые часто делают модели нелинейными, являются функции ЕСЛИ, МАХ, MIN, LN и ABS.

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

1. В задаче линейного программирования всегда присутствуют целевая функция (которую необходимо максимизировать или минимизировать) и ограничения.

2. Все функции (целевая функция и ограничения) в моделях ЛП являются линейными.

Искусство создания моделей ЛП

Чтобы описать управленческую ситуацию в виде символической (математической) мо­дели, полезно сначала составить "словесную модель". Это делается следующим образом

1. Описать словами цель и целевую функцию, т.е. показатель эффективности.

2. Дать словесное описание каждого ограничения, обращая особое внимание на то, является данное ограничение требованием в форме неравенств или равенством

3. Шаги 1 и 2 приведут к словесному описанию переменных решения.

Очень важно правильно определить переменные решения. Иногда существует не­сколько возможных вариантов. Например, должны ли переменные решения представ­лять килограммы готовой продукции или килограммы сырья? Советуем в этом случае за­дать вопрос: " Какие решения нужно принять, чтобы оптимизировать целевую функции?» Ответ на этот вопрос поможет правильно выявить переменные решения.

После выполнения пп. 1-3 следует присвоить обозначения (или имена) переменным решения. Затем необходимо выполнить такие действия.

4. Выразить все ограничения через обозначенные переменные решения.

5. Выразить с помощью обозначенных переменных целевую функцию.

На данном этапе следует проверить модель на соответствие единиц измерения. Напри­мер, если коэффициенты целевой функции даны в долларах за килограмм, то переменные решения, входящие в целевую функцию, должны выражаться в килограммах, а не в тоннax или унциях. Аналогично нужно проверить соответствие единиц измерения в правой и левой частях каждого ограничения. Например, если налагается ограничение на число часов рабо­чего времени, то в правой части ограничения должны быть указаны часы рабочего времени. Тогда, если переменные решения измеряются в килограммах, то значения коэффициентов для данной функции ограничения (т.е. числовые коэффициенты перед каждой переменной решения в левой части ограничения) должны выражаться в часах рабочего времени, делен­ных на килограмм. Нельзя допускать, чтобы в одной части равенства или неравенства стоя­ли часы, а в другой — минуты, секунды, килограммы или тонны.

Рассмотрим еще один аспект формирования модели ЛП. Как уже отмечалось, ограни­чения могут иметь форму неравенств типа "<=" или ">=". Студенты часто задают вопрос, бы­вают ли в модели линейного программирования ограничения в виде строгих неравенств ти­па "<" или ">", Ответ— нет. Причина этого имеет математическую природу: так делается для того, чтобы надлежащим образом сформулированная задача имела решение. Матема­тическое доказательство данного утверждения не входит в нашу задачу. Однако не будет преувеличением сказать, что практически в любой реальной жизненной ситуации, в которой встречаются ограничения, неравенств типа "<=" или ">=" вполне достаточно, что­бы передать реальный смысл. Например, если переменная А должна быть < =15, то в модели вполне можно использовать ограничение Х<= 14,9999999999.

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

4. Невозвратные и переменные издержки

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

Невозвратные издержки уже были сделаны, это означает, что никакие будущие решения не смогут повлиять на эти расходы. Предположим, было закуплено с последующей доставкой 800 и 500 фунтов алюминия двух сортов (1 и 2) по фиксированным ценам S5 и $ 10 за фунт со­ответственно, и контракт уже оплачен. Задача состоит в том, чтобы определить, как опти­мально использовать эти 1300 фунтов алюминия, чтобы максимизировать прибыль, получен­ную от производства алюминиевых шарниров и трубок. С каждым из двух изделий связан до­ход и переменные затраты на его производство (затраты на механическую обработку, штамповку и т.д.). При формировании модели невозвратные затраты $9000 на закупку алю­миния роли не играют. Эта сумма уже потрачена, следовательно, количество закупленного алюминия не является переменной решения. Переменными будут количества изделий, кото­рые следует произвести, и для их определения нужно учитывать только переменные издержки. Сформулируем модель, соответствующую данному описанию. Пусть

К— количество производимых шарниров (переменная решения);

С— количество производимых трубок (переменная решения);

S10 — доход от продажи одного шарнира;

$30 — доход от продажи одной трубки;

$4 — затраты на производство шарнира (переменные издержки);

$12 — затраты на производство трубки (переменные издержки).

Для каждого продукта мы должны вычислить удельную валовую прибыль, т.е. разность между удельным доходом и удельными переменными издержками. Удельная валовая прибыль составляет для шарниров $10 - $4= $6, для трубок $30 - $12 = $18.

Предположим, что для изготовления одного шарнира используется 1 фунт алюминия 1 сорта и 2 фунта алюминия 2 сорта. Для изготовления трубки требуется 3 фунта алюминия 1 сорта и 5 фунтов 2 сорта. Получается следующая модель линейного программирования.

Мах 6K + 18С

при ограничениях

К+ЗС<= 800 (ограничение на количество алюминия I сорта);

2К+ 5С<= 500 (ограничение на количество алюминия 2 сорта);

К>=0, С>=0.

Чтобы показать независимость решения от невозвратных издержек, заметим, что це­левая функция в нашей формулировке является суммарной валовой прибылью. Чистая прибыль вычисляется следующим образом: чистая прибыль = валовая прибыль — невоз­вратные издержки = 6К + 18С - 9000.

Найти допустимые значения К и С, максимизирующие выражение 6К+ 18С-9000 все равно, что найти допустимые значения К и С, максимизирующие выражение 6К+ 18С. Кон­станту 9000 можно игнорировать. Таким образом, если к оптимизируемой функции прибавить некую константу или умножить функцию на некоторое постоянное положительное число, ре­зультат оптимизации не изменится, т.е. оптимальные значения переменных решения останут­ся неизменными. Однако если прибавить (или отнять) одно и то же постоянное число ко всем коэффициентам переменных решения в целевой функции, результат может измениться.

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

5. Табличная модель компании

Напомним, что модель ЛП недельного производства компании Oak Product выглядит следующим образом (С— количество производимых стульев марки Captain, а М— коли­чество производимых стульев Mate).

Максимизировать 56С + 40М (целевая функция) при ограничениях

8С + 4М <= 1280 (ограничение для длинных штифтов);

4С+ 12М<= 1600 (ограничение для коротких штифтов);

4С + 4М<= 760 (ограничение для ножек);

С<= 140 (ограничение для прочных сидений);

М<= 120 (ограничение для облегченных сидений);

С+ М>= 100 (минимальный объем производства);

С>= 0 и М>= 0 (условия неотрицательности).

Обратите внимание на то, что ограничения были перегруппированы так, чтобы одно­типные неравенства находились рядом. Причина такой группировки станет понятна при описании работы средства Поиск решения. Табличная версия упрощенной модели Oak Product, созданная в рабочей книге Excel СтульЯ-xls, представлена на рис. 1. Здесь пока­зан случай, когда производится 110 стульев Captain и 90 стульев Mate. Заметим, что при та­ком ассортименте нарушается ограничение для ножек — их требуется больше, чем имеется.

Рис. 1. Упрощенная модель ЛП производства компании Oak Products

Совет. Наиболее простой способ ввода символов неравенства, таких как в ячейке Е6, со­стоит в том, чтобы ввести в ячейку символ <, а затем щелкнуть мышью на кнопке Под­черкнутый на панели инструментов форматирования Excel.

Хотя содержимое показанного рабочего листа в особых пояснениях не нуждается, следует сверить формулы на листе (см. рис. 1) с формулами математической модели производства компании Oak Production. Обратим ваше внимание на некоторые "неочевидные" аспекты данного рабочего листа.

Поиск по сайту: