Основы линейного программирования

Методы оптимальных решений

Контрольные вопросы по предмету

0


Подпишитесь на бесплатную рассылку видео-курсов:

Текст видеолекции

Методы оптимальных решений

Лекция 1

Тема лекции 1: «Основы линейного программирования»

Разделы лекции:

1. Основные элементы модели линейного программирования.
2. Графический анализ чувствительности. 
3. Общая задача линейного программирования.


РАЗДЕЛ 1. ОСНОВНЫЕ ЭЛЕМЕНТЫ МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

ЧТО ТАКОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ?

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

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (ЛП) – это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов. Линейное программирование (ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. ЛП успешно применяется в военной области, индустрии, сельском хозяйстве, транспортной отрасли, экономике, системе здравоохранения и даже в социальных науках. Широкое использование этого метода также подкрепляется высокоэффективными компьютерными алгоритмами, реализующими данный метод. На алгоритмах линейного программирования (учитывая их компьютерную эффективность) базируются оптимизационные алгоритмы для других, более сложных типов моделей и задач исследования операций (ИО), включая целочисленное, нелинейное и стохастическое программирование.  Вычисления в методе ЛП, как и во многих задачах ИО, как правило, очень трудоемкие и поэтому требуют применения вычислительной техники. Линейное программирование (планирование) служит для выбора наилучшего плана распределения ограниченных  однородных ресурсов в целях решения поставленной задачи.
В этом разделе на простых примерах с двумя переменными показаны основные элементы модели ЛП. Далее эти примеры будут обобщены в общую задачу линейного программирования.

ПРИМЕР 1.  Компания «Яркие краски» производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2. Следующая таблица представляет основные данные для задачи.

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

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

КАКИЕ ОСНОВНЫЕ ЭЛЕМЕНТЫ ВКЛЮЧАЕТ ЗАДАЧА (МОДЕЛЬ) ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

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

1. Переменные, которые следует определить.
2. Целевая функция, подлежащая оптимизации.
3. Ограничения, которым должны удовлетворять переменные.

Определение переменных – это первый шаг в создании модели. После определения переменных построение ограничений и целевой функции обычно не вызывает трудностей.

1. Переменные. В нашем примере необходимо определить ежедневные объемы производства краски для внутренних и наружных работ. Обозначим эти объемы как переменные модели: переменная  x1   –  это ежедневный объем производства краски для наружных работ (измеряется в тоннах);  переменная x2 – это ежедневный объем производства краски для внутренних работ (измеряется в тоннах).

2. Целевая функция. Используя эти переменные, далее строим целевую функцию. Логично предположить, что целевая функция, как суммарный ежедневный доход, должна возрастать при увеличении ежедневных объемов производства красок. Обозначим эту функцию через z: (суммарный ежедневный доход – функция z, измеряется в тысячах долларов) и положим, что  z=5х1+4х2.  В соответствии с целями компании получаем задачу:  максимизировать функцию z= 5х1 + 4х2.

3. Ограничения. Итак, остался не определенным последний элемент модели  - условия (ограничения), которые должны учитывать ограниченные возможности ежедневного потребления сырья и ограниченность спроса на готовую продукцию. Другими словами, ограничения на сырье можно записать следующим образом.

{ИСПОЛЬЗУЕМЫЙ ОБЪЕМ СЫРЬЯ ДЛЯ ПРОИЗВОДСТВА ОБОИХ ВИДОВ КРАСКИ}≤ {МАКСИМАЛЬНО ВОЗМОЖНЫЙ ЕЖЕДНЕВНЫЙ РАСХОД СЫРЬЯ}.

Из таблицы с данными имеем следующее.

Используемый объем сырья М1 = 6х1 + 4х2 (т);  используемый объем сырья М2 = 1х1 + 2х2 (т).

Так как ежедневный расход сырья М1 и М2 ограничен соответственно 24 и 6 тоннами, получаем следующие ограничения.  6х1+4х2≤24 (сырье М1); х1+2х2≤6 (сырье М2).
 
Существует еще два ограничения по спросу на готовую продукцию:

(1) максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 тонн, и

(2) ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ  более чем на одну тонну.

Первое ограничение (1) простое и записывается так: (х2≤2). Второе (2) можно сформулировать так: разность между ежедневными объемами производства красок для внутренних и наружных работ не должна превышать одной тонны, т. е. (х2–x1≤1).

Еще одно неявное ограничение состоит в том, что переменные х1 и х2 должны быть неотрицательными. Таким образом, к сформулированным выше ограничениям необходимо добавить условие неотрицательности переменных: х1≥0, х2≥ 0. Окончательно задача будет записана следующим образом: 

Максимизировать целевую функцию z(x1,x2)=5х1+4х2, 

при выполнении ограничений:
 
6х1 +4х2≤24,
х1+2х2≤6,
x2 – x1≤1,
х2≤2,
x1≥0, х2≥0.

КАКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ЯВЛЯЕТСЯ ДОПУСТИМЫМ?

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

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

В примере 1 целевая функция и все ограничения были линейными. Свойство линейности функций предполагает следующее.

1. Значения левых частей неравенств ограничений и значение целевой функции прямо пропорциональны значениям переменных.

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

ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

Мы покажем, как в задаче ЛП с двумя переменными можно получить решение графическим способом. Хотя такая задача редко встречается на практике (типовая задача ЛП обычно содержит тысячи переменных), идеи, вытекающие из графического способа нахождения оптимального решения, положены в основу построения общего метода решения задачи ЛП (называемого симплекс-методом). 

ИЗ КАКИХ ЭТАПОВ СОСТОИТ ГРАФИЧЕСКИЙ СПОСОБ  РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

Графический способ решения задачи ЛП состоит из двух этапов.

Этап 1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

Этап 2. Нахождение оптимального решения среди всех точек пространства допустимых решений.

Далее графический способ решения описан в двух вариантах: для максимизации и минимизации целевой функции.

ВАРИАНТ 1 . НАХОЖДЕНИЕ МАКСИМУМА ЦЕЛЕВОЙ ФУНКЦИИ

Мы используем модель, построенную для компании «Яркие краски» в примере 1, чтобы показать оба этапа графического решения задачи ЛП.

Этап 1. Построение пространства допустимых решений.

Сначала на плоскости проведем оси координат: на горизонтальной оси будут указываться значения переменной x1, а на вертикальной оси – значения переменной х2 (рисунок 1). Далее рассмотрим условие неотрицательности переменных: х1≥0 и х2≥0. Эти два ограничения показывают, что множество допустимых решений будет лежать в первом квадранте (т.е. выше оси х1 и правее оси х2).

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

Например, неравенство (6х1 + 4х2≤ 24) заменяется уравнением прямой (6х1 + 4х2 = 24). Чтобы провести эту прямую, надо найти две различные точки, лежащие на этой прямой. Можно положить х1=0, тогда х2=24/4= 6. Аналогично,  для х2=0 находим х1=24/6= 4. Итак,  прямая, заданная уравнением 6х1 + 4х2 = 24, проходит через две точки (0,6) и (4, 0). Эта прямая обозначена на рисунке 1 как линия (1).
 

Рисунок 1. Построение пространства допустимых решений.

Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость Ох1х2 на две полуплоскости, которые располагаются по обе стороны прямой, которая, как показано выше, соответствует данному неравенству. Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимая полуплоскость), а точки, лежащие по другую сторону, нет. Точкой, проверяющей, точки какой полуплоскости удовлетворяют неравенству, а какой - нет, может служить точка (0,0). Например, эта точка удовлетворяет первому неравенству (6х1+4х2≤ 24) (здесь 6•0 +4•0=0<24). Это означает, что точки полуплоскости, содержащей начальную точку (0,0), удовлетворяют этому неравенству. На рисунке 1 допустимые полуплоскости показаны стрелочками.  В том случае, когда точка (0,0) не удовлетворяет неравенству, допустимой полуплоскостью будет та, которая не содержит эту точку. Если же прямая проходит через эту точку (0,0), то следует в качестве «тестовой» взять какую-либо другую точку.

Этап 2. Нахождение оптимального решения.

Точки пространства допустимых решений, показанного на рисунке 1 , удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, Е и Е. Любая точка, расположенная внутри или на границе области, ограниченной ломаной АВСDЕF, является допустимым решением, т.е. удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.
Нахождение оптимального решения требует определения направления возрастания целевой функции (z=5х1+4х2) (напомним, что мы максимизируем функцию z). Мы можем приравнять z к нескольким возрастающим значениям, например, к 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых. Для значений 10 и 15 получаем следующие  уравнения прямых:  (5х1+4х2=10) и (5х1+4х2=15). На рисунке 2 эти прямые показаны штриховыми линиями, а направление возрастания целевой функции z - толстой стрелкой. Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции, и будет точкой оптимума.
 
Рисунок 2. Нахождение оптимального решения.

На рисунке 2 видно, что оптимальное решение соответствует точке С. Эта точка является точкой пересечения прямых (1) и (2), поэтому ее координаты х1 и х2 находятся как решение системы уравнений, задающих эти прямые:

6х1+4х2=24,
х1+2х2=6. 

Решением этой системы будет точка: х1=3 и х2=1,5. При этом значение целевой функции z в данной точке равно = 5х1+ 4х2=15+6=21 . Полученное решение означает, что для компании «Яркие краски» оптимальным выбором будет ежедневное производство 3 тонны краски для наружных работ и 1,5 тонны для внутренних работ с ежедневным доходом в $21 000.

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

ВАРИАНТ 2. НАХОЖДЕНИЕ МИНИМУМА ЦЕЛЕВОЙ ФУНКЦИИ.
 
ПРИМЕР 2. (ЗАДАЧА О ДИЕТЕ).
 
Фармацевтическая фирма «Здоровое питание» ежедневно производит не менее 800 килограммов  некой пищевой добавки, которая состоит из смеси кукурузной и соевой муки, состав которой представлен в следующей таблице.

Мука    Белок    Клетчатка     Стоимость (в $ за килограмм)
    (в килограммах на килограмм муки)   
Кукурузная    0,09    0,02    0,30
Соевая    0,60    0,06    0,90


Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма «Здоровое питание» хочет определить рецептуру смеси наименьшей стоимости с учетом требований диетологов.

1. Переменные. Поскольку пищевая добавка состоит только из кукурузной и соевой муки, переменными для этой задачи, очевидно, будут: переменная x1  - это количество (в килограммах) кукурузной муки, используемой в дневном производстве пищевой добавки;  переменная x2 – это количество (в килограммах) соевой муки, используемой в дневном производстве пищевой добавки.

2. Целевая функция. Целевая функция равна общей стоимости пищевой добавки, производимой за один день, и должна быть минимальной. В данном случае это можно записать следующим образом:  минимизировать функцию z(x1,x2)=0,3х1+0,9х2.
 
3. Ограничения.  Ограничения модели должны отражать производственные требования и рекомендации диетологов. Фирма должна выпускать не менее 800 килограммов смеси в день; соответствующее ограничение будет записано следующим образом:  x1+х2≥800.
Рассмотрим ограничение, связанное с количеством белка в пищевой добавке. Общее количество белка в смеси, состоящей из х1 кг кукурузной муки и х2 кг соевой муки, равно (0,09х1 + 0,6х2) (кг). Это количество должно составлять не менее 30% от общего объема смеси (х1+х2). Отсюда получаем следующее неравенство: 0,09х1+0,6х2≥0,3(х1+х2).
Аналогично строится ограничение для клетчатки:  0,02х1+0,06х2≤0,05(х1+х2).  В последних двух неравенствах переменные х1 и х2 надо перенести из правых частей неравенств в левые.

Окончательно модель примет следующий вид:

Минимизировать  функцию z(x1,x2)=0,3х1+0,9х2;

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

x1 +х2≥800;
0,21х1 – 0,3х2 ≤0;
0,03х1 – 0,01х2≥0;
x1≥0;  x2≥0.

Этап 1. Построение пространства допустимых решений.

На рисунке 3 показано графическое решение этой задачи. В отличие от модели примера 1, здесь две прямые, соответствующие неравенствам ограничений, проходят через начальную точку (0,0). Для того, чтобы провести на графике такую прямую, необходима еще одна точка. Координаты этой точки можно найти, подставив в уравнение прямой любое значение для одной переменной и затем из этого уравнения найти значение для другой. Например, для второго неравенства 0,21х1–0,3х2≤0 из системы ограничений положим х1=200, тогда для второй переменной получаем уравнение 0,21•200–0,3х2= 0; отсюда имеем: (х2 = 42/0,3 =140). Таким образом, прямая  (0,21х1–0,3х2=0) проходит через точки (0,0) и (200, 140). Заметим также, в данном случае для определения допустимой полуплоскости нельзя использовать в качестве «тестовой» точку (0,0), здесь следует взять какую-либо другую, например (100, 0) или (0,100).
 
Рисунок 3. Построение пространства допустимых решений.
Этап 2. Нахождение оптимального решения.

Поскольку в данной модели следует минимизировать целевую функцию, поэтому нужно идти в направлении уменьшения ее значений (это направление на рисунке 3 показано стрелкой).  Оптимальное решение находится на пересечении прямых (x1+x2=800) и (0,21х1–0,3х2=0), откуда получаем: (х1=470,59 (кг) и х2=329,41 (кг). При этих значениях переменных минимальная стоимость производимой ежедневно пищевой добавки составляет z{min}=0,3•470,51+ 0,9•329,41=437,65 (долларов).
 
ЧТО ТАКОЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЫЕ?

В обоих примерах 1 и 2 этого раздела мы использовали неравенства типа «< или равно»  (знак неравенства ≤) и «> или равно»  (знак неравенства ≥). В этих примерах также предполагалась неотрицательность всех переменных. В данном разделе мы введем два типа дополнительных неотрицательных переменных (назовем их остаточными и избыточными), которые связаны с неравенствами типа « ≤ » и « ≥ » соответственно.

ЗАМЕЧАНИЕ. Отметим, что в русской математической литературе для этих типов переменных не используются какие-либо специальные названия - они известны просто как дополнительные переменные (хотя иногда их также называют балансными). В неравенствах они различаются тем, что перед остаточной переменной всегда стоит знак «плюс», а перед избыточной  - знак «минус».

Введем также понятие свободной переменной, которая может принимать как положительные, так и отрицательные значения (и, конечно, значение 0).

ЧТО ТАКОЕ ОСТАТОЧНАЯ ПЕРЕМЕННАЯ?

ОСТАТОЧНАЯ ПЕРЕМЕННАЯ.   Неравенства типа « ≤ » обычно можно интерпретировать как ограничения на использование некоторых ресурсов (представленных в левой части неравенств переменными модели). В такой интерпретации остаточная переменная показывает  количество неиспользованных ресурсов. В примере с компанией «Яркие краски» неравенство 6х1+4х2≤24 связано с использованием сырья М1. Это неравенство эквивалентно равенству 6х1+4х2+s1=24, где s1≥0. Здесь остаточная переменная s1(=24 – 6х1 – 4х2) равна неиспользуемому количеству сырья М1.

ЧТО ТАКОЕ ИЗБЫТОЧНАЯ ПЕРЕМЕННАЯ?

ИЗБЫТОЧНАЯ ПЕРЕМЕННАЯ. Неравенство типа « ≥ »показывает, что «что-то» должно быть не меньше определенной величины. Избыточная переменная определяет превышение значения левой части неравенства над этой величиной. Например, в задаче «о диете» неравенство х1+х2≥800 показывает, что суточное производство пищевой добавки не должно быть меньше 800 килограммов. Математически это неравенство эквивалентно равенству: (x1+x2–V1=800), где V1≥0. Положительное значение избыточной переменной V1 показывает превышение суточного производства добавки над минимальным значением в 800 кг.

СВОБОДНАЯ ПЕРЕМЕННАЯ. В приведенных выше примерах условие неотрицательности переменных является естественным. Но, конечно, возможны ситуации, когда переменные могут принимать любые действительные значения. Такая ситуация показана в следующем примере.

ПРИМЕР 3. Ресторан быстрого обслуживания «Сочный Бургер»  торгует порционными мясными пирогами и чизбургерами. На порцию мясного пирога идет четверть килограмма мяса, а на чизбургер  - только 0,2 килограмма. В начале рабочего дня в ресторане имеется 200 кг мяса, можно еще прикупить мясо в течение дня, но уже с наценкой в 25 центов на каждый килограмм мяса. Мясо, оставшееся в конце рабочего дня, жертвуется благотворительной организации «Горячий суп». Ресторан имеет доход 20 центов от одной порции мясного пирога и 15 центов от одного чизбургера. Как и многие другие, этот ресторан не может продать в день более 900 бутербродов. Какова должна быть доля каждого из бутербродов (т.е. сколько порций мясного пирога и сколько чизбургеров) в ежедневном производстве ресторана, чтобы максимизировать его доход?

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

2. Ограничения. Сначала рассмотрим ограничения. Для производства мясных пирогов и чизбургеров ресторан может ограничиться 200 килограммами мяса или может прикупить еще. В первом случае получаем ограничение в виде неравенства 0,25x1+0,2х2≤200, а во втором 0,25x1+0,2х2≥200. Естественно, выбор одного из этих неравенств будет существенно влиять на возможное оптимальное решение. Так как мы не знаем, какое из них необходимо, логично заменить их одним равенством: 0,25х1+0,2х2+х3 = 200, где х3 – это свободная переменная. Фактически свободная переменная х3 в данной ситуации одновременно играет роли как остаточной, так и избыточной переменных.

3. Целевая функция. Далее построим целевую функцию, Ресторан хочет максимизировать свой доход. Очевидно, что для максимизации дохода желательно как можно больше продавать своей продукции, но для этого необходимы дополнительные закупки мяса.  В этом случае переменная х3 должна быть отрицательной, т.е. должна играть роль избыточной переменной.  Для того чтобы раскрыть «двойственную» природу переменной х3, используем стандартный математический прием, а именно представим ее в следующем виде.

х3=(x3+)–(x3-), где (х3+)≥0, (x3-)≥0.

Если (x3+)>0 и (х3-)=0, тогда переменная х3 играет роль остаточной. Если, напротив, (x3-) >0 и (x3+)=0, тогда переменная х3 выступает в роли  избыточной. В лекции 2 будет показана ситуация, когда оптимальное решение задачи линейного программирования достигается при положительных значениях как (х3+) , так и (х3-). Итак, теперь ограничение можно записать в виде равенства:

0,25х1+0,2х2+(х3+) – (x3-)=200.

Целевая функция получает следующее выражение.  Максимизировать Z= 0,2x1+0,15x2 – 0,25(x3-).

РАЗДЕЛ 2.  ГРАФИЧЕСКИЙ АНАЛИЗ ЧУВСТВИТЕЛЬНОСТИ.
 
Модель линейного программирования является как бы «моментальным снимком» реальной ситуации, когда параметры модели (коэффициенты целевой функции и неравенств ограничений) предполагаются неизменными. Естественно изучить влияние изменения параметров модели на полученное оптимальное решение задачи ЛП. Такое исследование называется анализом чувствительности. В этом разделе лекции анализ чувствительности основывается на графическом решении задачи ЛП. Рассмотрим два случая: (1) изменение коэффициентов целевой функции и (2) изменение значений констант в правой части неравенств ограничений. Хотя проведенное здесь исследование будет элементарным и ограниченным, оно покажет основные идеи методов анализа чувствительности. Подробно методы этого анализа описаны в монографии [2].

СЛУЧАЙ 1. ИЗМЕНЕНИЕ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ.

В общем виде целевую функцию задачи ЛП с двумя переменными можно записать следующим образом.  Максимизировать или минимизировать целевую функцию: z=с1х1+с2х2.
 
Изменение значений коэффициентов с1 и с2 приводит к изменению угла наклона прямой z=с0. Графический способ решения задачи ЛП, описанный в разделе 1 этой лекции, показывает, что это может привести к изменению оптимального решения: оно будет достигаться в другой угловой точке пространства решений. Вместе с тем, очевидно, существуют интервалы изменения коэффициентов с1 и с2, когда текущее оптимальное решение сохраняется. Задача анализа чувствительности и состоит в получении такой информации. В частности, представляет интерес определение интервала оптимальности для отношения (с1/с2) (или, что то же самое, для с2/с1); если значение отношения с1/с2 не выходит за пределы этого интервала, то оптимальное решение в данной модели сохраняется неизменным. Следующий пример показывает, как можно получить необходимый результат с помощью анализ графического представления модели ЛП. 

ПРИМЕР 1 (ПРОДОЛЖЕНИЕ).  Применим процедуру анализа чувствительности к задаче примера 1(модель для компании «Яркие краски»). На рисунке 4 видно, что функция z= 5х1 + 4х2 достигает максимального значения в угловой точке С. При изменении коэффициентов целевой функции z= с1х1 + с2х2 точка С останется точкой оптимального решения до тех пор, пока угол наклона линии будет лежать между углами наклона двух прямых,  пересечением которых является точка С. Этими прямыми являются 6х1+4х2=24 (ограничение на сырье М1) и х1+2х2=6 (ограничение на сырье М2). Алгебраически это можно записать следующим образом:
4/6 ≤с2/с1≤2/1, с1≠0; (*)
или
1/2 ≤с1/с2≤6/4, с2≠0. (**)

В первой системе неравенств (*) условие с1≠0 означает, что прямая, соответствующая целевой функции, не может быть горизонтальной.  Аналогичное условие с2≠0 в следующей системе неравенств (**) означает, что эта же прямая не может быть вертикальной. Из рисунка 4 видно, что интервал оптимальности данной задачи (он определяется двумя прямыми, пересекающимися в точке С) не разрешает целевой функции быть ни горизонтальной, ни вертикальной прямой. Таким образом, мы получили две системы неравенств, определяющих интервал оптимальности в нашем примере. Когда с1 и с2 могут принимать нулевые значения, интервал оптимальности для отношения с1/с2 (или с2/с1) необходимо разбить на два множества, где знаменатели не обращались бы в нуль.
 
Рисунок 4. Изменение коэффициентов целевой функции.

Итак, если коэффициенты с1 и с2 удовлетворяют приведенным выше неравенствам, оптимальное решение будет достигаться в точке С. Отметим, если прямая z=с1х1+с2х2 совпадет с прямой х1+2х2=6, то оптимальным решением будет любая точка отрезка СD. Аналогично, если прямая, соответствующая целевой функции, совпадет с прямой 6х1+4х2=24, тогда любая точка отрезка СB будет оптимальным решением. Однако заметим, что в обоих случаях точка С остается точкой оптимального решения.
Приведенные выше неравенства можно использовать при определении интервала оптимальности для какого-либо одного коэффициента целевой функции, если предположить, что другой коэффициент остается неизменным. Например, если в нашей модели зафиксировано значение коэффициента с2 (пусть с2=4), тогда интервал оптимальности для коэффициента с1 получаем из неравенств

1/2≤с1/с2≤6/4, с2≠0;

путем подстановки туда значения с2=4. После выполнения элементарных арифметических операций получаем неравенства для коэффициента с1:  2≤с1≤6.
Аналогично, если зафиксировать значение коэффициента с1 (например, с1=5), тогда из неравенств

4/6 ≤с2/с1≤2/1, с1≠0;

получаем интервал оптимальности для коэффициента с2: 10/3≤с2≤10.

СЛУЧАЙ 2. СТОИМОСТЬ РЕСУРСОВ.

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

ПРИМЕР 1(ПРОДОЛЖЕНИЕ).  В модели для компании «Яркие краски» (пример 1) первые два неравенства представляют собой ограничения на использование сырья М1 и М2,  соответственно. Определим стоимость единиц этих ресурсов.  Начнем с ограничения для сырья М1. Напомним, что в данной задаче оптимальное решение достигается в угловой точке С, являющейся точкой пересечения прямых, соответствующих ограничениям на сырье М1 и М2 (рисунок 5).
 
Рисунок 5. Изменение количества доступного ресурса M1.

При изменении уровня доступности материала М1 (увеличение или уменьшение текущего уровня, равного 24 тоннам) точка С оптимального решения «плывет» вдоль отрезка DG. Любое изменение уровня доступности материала М1, приводящее к выходу точки пересечения С из этого отрезка, ведет к неосуществимости оптимального решения в точке С. Поэтому можно сказать, что концевые точки D(2, 2) и G=(6, 0) отрезка DG определяют интервал осуществимости для ресурса М1 . Количество сырья М1, соответствующего точке D(2,2), равно 6х1+4х2=6•2+4•2=20 (тонн). Аналогично количество сырья, соответствующего точке G(6,0), равно 6•6+4•0=36 (тонн). Таким образом, интервал осуществимости для ресурса М1 составляет 20≤М1≤36 (здесь через М1 обозначено количество материала М1).  Если мы определим М1 как М1=24+B1,  где В1 отклонение количества материала M1 от текущего уровня в 24 тонны, тогда последние неравенства можно переписать как  20≤24+D1≤36 или (–4≤D1≤12). Это означает, что текущий уровень ресурса М1 может быть уменьшен не более чем на 4 тонны и увеличен не более чем на 12 тонн. В этом случае гарантируется, что оптимальное решение будет достигаться в точке С – точке пересечения прямых,  соответствующих ограничениям на ресурсы М1 и М2.

Теперь вычислим стоимость единицы материала М1. При изменении количества сырья М1 от 20 до 36 тонн, значения целевой функции z будут соответствовать положению точки С на отрезке DG. Обозначив через Y1 стоимость единицы ресурса М1 , получим следующую формулу.

Y1={изменение значения z при перемещении точки С от D до G}/{изменение количества М1 при перемещении т. С от D до G}.

Если точка С совпадает с точкой D(2, 2), то 5х1+4х2=18 (тысяч долларов), если же точка С совпадает с точкой G(6,0), тогда 5х1+4x2=30 (тысяч долларов). Отсюда следует, что 

Y1={30 – 18}/{36 – 20}=12/16=3/4 (тысяч долларов на тонну материала М1).

Этот результат показывает, что изменение количества ресурса М1 на одну тонну (если общее количество этого ресурса не меньше 20 и не больше 36 тонн) приводит к изменению в оптимальном решении значения целевой функции на $750.

Теперь рассмотрим ресурс М2. На рисунка 6 видно, что интервал осуществимости для ресурса М2 определяется концевыми точками В и Н отрезка ВН, где B=(4, 0) и Н=(8/3,2). Точка Н находится на пересечении прямых (ЕD) и (ВС).
 

Рисунок 6. Изменение количества доступного ресурса M2.
Находим, что количество сырья М2, соответствующего точке В(4,0), равно х1+2х2=4+0=4 (тонны), а точке Н(8/3,2) равно х1+2х2=8/3+4=20/3 (тонн). Значение целевой функции в точке В(4,0) равно 5х1+4х2=5•4+4•0=20 (тысяч долларов), а в точке Н(8/3,2) равно  5х1+4х2=5•8/3+4•2=64/3 (тысяч долларов). Отсюда следует, что количество сырья М2 может изменяться от 4 до 20/3 тонн, а стоимость единицы ресурса М2, обозначенная как Y2, равна

Y2={64/3 – 20}\{20/3 – 4}={4/3}/{8/3}=1/2 (тысяч долларов на тонну материала М2).

Этот результат показывает, что изменение количества ресурса М2 на одну тонну (если общее количество этого ресурса не меньше 4 тонн и не больше 20/3 тонн) приводит к изменению в оптимальном решении значения целевой функции на $500.

РАЗДЕЛ 3. ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

На простых примерах  в первом разделе лекции мы описали основные элементы модели линейного программирования – математического метода отыскания максимума или минимума линейной  функции при наличии ограничений в виде линейных неравенств или уравнений.

ЧТО ТАКОЕ ЦЕЛЕВАЯ ФУНКЦИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

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

КАКИЕ ХАРАКТЕРНЫЕ ЧЕРТЫ ИМЕЮТ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

Характерные черты задач ЛП следующие:

1) показатель оптимальности – целевая функция z(X) представляет собой линейную функцию от элементов решения X = (x1,x2,...,xn );

2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

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

ЧТО ОЗНАЧАЕТ ПРОПОРЦИОНАЛЬНОСТЬ МОДЕЛИ?

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

ЧТО ОЗНАЧАЕТ АДДИТИВНОСТЬ МОДЕЛИ?

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

ОБЩАЯ ФОРМА ЗАПИСИ ЗАДАЧИ ЛП.

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

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

z(X)= c1x1 + c2x2 + ... + cnxn →max (min)

(линейной функции элементов решения x1, x2, …, xn)  при линейных ограничительных условиях, накладываемых на элементы решения:
 
где аik, bi, ck  – заданные числа.

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

ПРАВИЛО СОКРАЩЕННОГО СУММИРОВАНИЯ.  Для обозначения суммы чисел: a1+a2+…+an принята запись:

n
∑ ak,
k=1

где ∑ - знак суммирования, а k – индекс суммирования.

Это обозначение очень удобно:
 
А вот как выглядит запись общей задачи линейного программирования:
 

где xk - искомые величины, содержащие решение поставленной задачи; аik, bi, ck -  известные постоянные величины,  характеризующие условия задачи.

ЧТО ТАКОЕ ДОПУСТИМОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

Допустимое решение – это совокупность чисел (план) X =(x1, x2, …, xn), удовлетворяющих ограничениям задачи ЛП.

ЧТО ТАКОЕ ОПТИМАЛЬНОЕ ДОПУСТИМОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?
 
Оптимальное допустимое решение – это план, при котором ЦФ принимает свое экстремальное значение.

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


СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

[1] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. СПб.: Союз, 1999. — 320 с.

[2] Таха Х.А. Введение в исследование операций. — 6-е изд. Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с: ил.

[3] Шелобаев С. И. Математические методы и модели в экономике,  финансах, бизнесе: Учебное пособие для вузов. — М.: ЮНИТИ - ДАНА, 2001. - 367 с.
[4] Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический университетский учебник»).

[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш,  Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. - 391 с.