Лекция по информатике. Тема Введение в линейное программирование (ЛП)

• Название: Тема Введение в линейное программирование (ЛП)
• Анкор: Лекция по информатике
• Дата: 23.05.2022
• Размер: 244.04 Kb.
• Имя файла: vved_v_lp_lekciya.pdf
• Тип: Задача; #544621

1
Тема 2. Введение в линейное программирование (ЛП)
Цель: научить распознавать основные проблемные ситуации, кото- рые могут быть формализованы в виде задачи линейного программиро- вания, познакомить с геометрическим методом нахождения оптимально- го решения и анализом оптимального решения на чувствительность.
Задачи:
 ввести понятие задачи линейного программирования (задачи ЛП);
 научить формализовывать проблемы, приводящие к задачам ЛП;
 ввести понятия допустимого и оптимального решений, значения за- дачи ЛП;
 научить находить оптимальное решение задачи ЛП геометрическим методом;
 дать представление об анализе оптимального решения ЛП на чув- ствительность.
Оглавление
§ 2.1.
Правила построения математической модели. Примеры задач ли- нейного программирования.
§
2.2. Задача линейного программирования.
§
2.3. Геометрическая структура множества допустимых решений задачи линейного программирования.
§
2.4. Геометрический метод решения задачи линейного программирова- ния.
§
2.5. Анализ оптимального решения на чувствительность.
§ 2.1.
Правила построения математической модели.
Примеры задач линейного программирования
Линейное программирование или сокращенно ЛП (Linear Program- ming, LP) –
это раздел более общей теории математического программирования (Mathematical Programming, MP). Математическое
программирование занимается изучением проблем принятия решений, которые могут быть математически сформулированы как задачи нахож- дения максимума (минимума) некоторой, вообще говоря, нелинейной функции (целевой функции) многих переменных, при заданной системе ограничений на основные переменные задачи.
Формализация проблемы как задачи ЛП подразумевает следующие этапы:
 понять проблему, составить описательную модель задачи;
 идентифицировать основные переменные задачи;
 выбрать некоторую количественную меру эффективности для целевой функции;

2
 представить эту меру эффективности как линейную функцию относительно основных переменных;
 идентифицировать и представить все ограничения как линейные уравнения или неравенства относительно основных переменных;
 собрать количественные данные или сделать соответствующие оценки для всех параметров модели.
Основные математические предположения для задачи ЛП (основ- ные ограничения на применение):
 определенность (детерминированность) – предполагается, что все параметры модели известны точно или могут быть оценены;
 линейность (эквивалентна пропорциональности и аддитивности)
–
предполагается, что все функциональные соотношения модели линейны относительно основных переменных;
o
пропорциональность – предполагается, что эффект влияния основной переменной задачи пропорционален значению этой переменной; o
аддитивность – предполагается, что эффект влияния нескольких основных переменных задачи равен сумме эффектов от каждой переменной;
 делимость – предполагается, что все основные переменные задачи могут принимать произвольные вещественные значения в опре- деленном диапазоне (бесконечно делимы).
Рассмотрим несколько задач, которые можно сформулировать как задачи линейного программирования.
Пример 2.1.1. (Построение оптимального плана производства)
Кондитерская фабрика производит продукцию двух видов: конфеты и шоколад. Для производства продукции каждого вида требуются ресур- сы двух типов: сахар и какао-бобы. Для производства одной тонны про- дукции каждого вида требуется по одной тонне сахара. Для производства одной тонны шоколада требуется 5 тонн какао, а для производства од- ной тонны конфет – 2 тонны какао. Суточные запасы ресурсов равны 4 и
10 тонн соответственно. Прибыль от реализации одной тонны шоколада и конфет составляет 5 и 3 тысячи рублей соответственно. Написать ма- тематическую модель для нахождения оптимального (т. е. максимизи- рующего прибыль) суточного плана производства.
Основные данные задачи можно представить в виде таблицы:
Расход ресурсов на 1 тонну готовой продукции
Исходные ресурсы
Шоколад
Конфеты
Запас ресурса
Сахар
1 1
4
Какао
5 2
10
Прибыль
5 3

3
Определим основные составляющие задачи линейного программи- рования.
Переменные:
1
x –
суточный объем производства шоколада,
2
x –
суточный объем производства конфет.
Целевая функция: общая прибыль от реализации суточного плана

1 2
( ,
)
x
x x
определяется линейной функцией 

1 2
5 3
z
x
x .
Ограничения: содержательно ограничения на запас ресурсов мож- но записать следующим образом













Расход
Запас ресурса ресурса
, используя данные таблицы, получаем линейные ограничения
 на расход сахара


1 2
4
x
x
;
 на расход какао-бобов


1 2
5 2
10
x
x
;
 на знак переменных


1 2
0,
0
x
x
Окончательно задача принимает вид:


1 2
max max(5 3
)
z
x
x при выполнении ограничений






1 2
1 2
1 2
4;
5 2
10;
0,
0.
x
x
x
x
x
x
Пример 2.1.2. (Формирование смеси минимальной стоимости)
Фармацевтическая фабрика ежедневно производит не менее 800 фунтов пищевой добавки – смеси кукурузной и соевой муки, состав кото- рой представлен в таблице (в фунтах на фунт муки):
Мука
Кукуруза
Соевая
Белок
0,09 0,6
Клетчатка
0,02 0,06
Стоимость (в долл. за фунт)
0,3 0,9
Диетологи требуют, чтобы в пищевой добавке было не менее 30 % белка и не более 5 % клетчатки. Фирма хочет определить рецептуру сме- си минимальной стоимости с учетом требований диетологов.
Переменные:
1
x –
количество кукурузной муки, используемой в дневном произ- водстве пищевой добавки;

4 2
x –
количество соевой муки, используемой в дневном производстве пищевой добавки.
Целевая функция: требуется минимизировать общую стоимость произведенной пищевой добавки, которая может быть вычислена с по- мощью линейной функции


1 2
0,3 0,9
z
x
x .
Ограничения:
 на количество производимой смеси


1 2
800
x
x
;
 на количество белка в пищевой добавке





1 2
1 2
0,09 0,6 0,3
x
x
x
x
;
 на количество клетчатки в пищевой добавке





1 2
1 2
0,02 0,06 0,05
x
x
x
x
;
 на знак переменных


1 2
0,
0.
x
x
После переноса переменных в левую часть ограничений задача примет вид:




1 2
min min 0,3 0,9
z
x
x
при ограничениях








1 2
1 2
1 2
1 2
800;
0,21 0,3 0;
0,03 0,01 0;
0,
0.
x
x
x
x
x
x
x
x
Пример 2.1.3. (Поиск оптимального плана производства)
Автомобильная компания производит легковые автомобили и гру- зовики. Каждое транспортное средство должно обрабатываться в покра- сочном и сборочном цехах. Если бы в покрасочном цехе обрабатывались только грузовые автомобили, то можно было бы покрасить 40 машин в день. Если бы обрабатывались только легковые автомобили, то выпуск составил бы 60 единиц продукции. В сборочном цехе обрабатывается 50 транспортных средств в день. Прибыль от производства одного легково- го автомобиля и грузовика составляет 200$ и 300$ соответственно. Оп- ределить оптимальный ежедневный выпуск продукции, обеспечивающий максимальную прибыль компании.
Переменные:
1
x –
количество грузовиков, производимых ежедневно;
2
x – количество автомобилей, производимых ежедневно.
Ограничения:
 на время использования покрасочного цеха


1 2
1 1
1 40 60
x
x
, где

5 1
40
–
время (в днях), идущее на покраску одного грузовика;
1 60
–
время (в днях), идущее на покраску одного автомобиля;
 на время использования сборочного цеха


1 2
50
x
x
;
 на знак переменных


1 2
0,
0.
x
x
Целевая функция:
Суммарный доход компании определяется функцией


1 2
300 200
z
x
x .
Окончательно имеем задачу




1 2
max max 300 200
z
x
x
при ограничениях






1 2
1 2
1 2
3 2
120;
50;
0,
0.
x
x
x
x
x
x
Замечание 2.1.1. Поскольку переменные задачи характеризуют план выпуска транспортных средств, они могут принимать только цело- численные значения, т.е. свойство делимости в данной задаче не выпол- няется. Однако отмеченная проблема легко преодолима. Например, если в процессе решения задачи получим оптимальный план ежедневного выпуска




 



*
*
1 2
1 1
,
2 ,3 2
4
x x
,
то это эквивалентно рекомендации произво- дить 10 грузовиков и 13 легковых автомобилей за 4 дня.
Пример 2.1.4. (Определение кредитной политики банка)
Банк, предоставляющий полный набор банковских услуг, находится в процессе формирования портфеля кредитов объемом 12 млн. дол. В таблице представлены возможные типы банковских кредитов.
Тип кредита
Ставка кредита
Вероятность безнадежных долгов
Нецелевые кредиты
0,14 0,1
На покупку автомобилей
0,13 0,07
На покупку жилья
0,12 0,03
Сельскохозяйственные
0,125 0,05
Коммерческие
0,1 0,02
Конкурентная борьба с другими финансовыми институтами вынуж- дает банк не менее 40 % капитала помещать в сельскохозяйственные и

6
коммерческие кредиты. Для содействия строительной индустрии банк планирует вложить в кредиты на покупку жилья не менее 50 % от общей суммы нецелевых кредитов, кредитов на покупку автомобилей и жилья.
Максимально возможная доля безнадежных долгов в кредитном порт- феле составляет 4 %.
Переменные:
1
x –
сумма нецелевых кредитов;
2
x – сумма кредитов на покупку автомобилей;
3
x – сумма кредитов на покупку жилья;
4
x – сумма сельскохозяйственных кредитов;
5
x – сумма коммерческих кредитов.
Целевая функция: банк максимизирует прибыль, т. е. разность ме- жду доходом и ожидаемой суммой невозвращенных кредитов, которую можно вычислить так:
















1 2
3 4
5 1
2 3
4 5
0,14 0,9 0,13 0,93 0,12 0,97 0,125 0,95 0,1 0,98 0,1 0,07 0,03 0,05 0,02 .
z
x
x
x
x
x
x
x
x
x
x
Ограничения:
 на общую сумму кредитов





1 2
3 4
5 12
x
x
x
x
x
;
 на сельскохозяйственные и коммерческие кредиты






4 5
1 2
3 4
5 0,4(
)
x
x
x
x
x
x
x ;
 на покупку жилья





3 1
2 3
0,5
x
x
x
x
;
 на невозвращенные кредиты









1 2
3 4
5 1
2 3
4 5
0,1 0,07 0,03 0,05 0,02 0,04
x
x
x
x
x
x
x
x
x
x
;
 условия неотрицательности переменных

1 2
3 4
5
,
,
,
,
0
x x x x x
После приведения подобных членов в целевой функции и преоб- разования ограничений, получаем задачу:





1 2
3 4
5
max
0,026 0,0509 0,0864 0,06875 0,078
z
x
x
x
x
x при ограничениях



















1 2
3 4
5 1
2 3
4 5
1 2
3 1
2 3
4 5
1 2
3 4
5 12;
0,4 0,4 0,4 0,6 0,6 0;
0,5 0,5 0,5 0;
0,06 0,03 0,01 0,01 0,02 0;
,
,
,
,
0.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x x x x x

7
§ 2.2
. Задача линейного программирования (задача ЛП)
Математически задача ЛП – задача нахождения наибольшего
(наименьшего) значения линейной функции многих переменных при ли- нейных ограничениях типа равенств (неравенств), когда на переменные задачи есть (нет) ограничений на знак.
В общем случае задача линейного программирования может быть записана следующим образом:
 задача максимизации




1 1
max max(
)
n
n
z
c x
c x
(2.2.1) при ограничениях







1 1
,
1, ,
0,
1, .
i
in
n
i
j
a x
a x
b i
m
x
j
n
(2.2.2)
 задача минимизации




1 1
min min(
)
n
n
z
c x
c x
(2.2.3) при ограничениях







1 1
,
1, ,
0,
1, .
i
in
n
i
j
a x
a x
b i
m
x
j
n
(2.2.4)
Здесь

,
1,
j
x j
n
– переменные модели,




1 1
n
n
z
c x
c x –
целевая функция,




1 1
i
in
n
i
a x
a x
b –
ограничение с номером
i
,  1,
i
m ,
 0
j
x
–
условие неотрицательности переменной j,
 1,
j
n
,

,
,
j
ij
i
с a b
заданные параметры
,
 1,
i
m
,
 1,
j
n
Вектор


1
(
,
,
)
n
X
x
x
, удовлетворяющий ограничениям задачи, на- зывается допустимым решением задачи ЛП.
Допустимым множеством решений задачи ЛП называется множе- ство векторов


1
(
,
,
)
n
X
x
x
, удовлетворяющих всем ограничениям за- дачи.
Вектор





1
(
,
,
)
n
X
x
x
, доставляющий максимум (минимум) функции
z
при заданных ограничениях, называется оптимальным решением за- дачи
ЛП.
Соответственно, наибольшее
 


*
z
z X
(наименьшее
 


*
z
z X
) значение целевой функции называется значением задачи ЛП.
Решить задачу ЛП означает найти оптимальное решение





1
(
,
,
)
n
X
x
x
и соответствующее значение целевой функции
 
*
z x
, т. е. значение задачи ЛП.

8
§ 2.3.
Геометрическая структура множества допустимых решений в
задаче линейного программирования
Приведем некоторые понятия из теории выпуклых множеств и сформулируем теорему о геометрической структуре множества допусти- мых решений в задаче ЛП.
Напомним, что элементы пространства
n
R
называются как точками, так и векторами.
Множество

n
M
R
называется выпуклым, если для двух любых то- чек

1 2
,
X X
M
и любого


  0,1
выполняется условие:







1 2
1
X
X
M
Другими словами, множество называется выпуклым, если с любы- ми двумя точками из этого множества ему принадлежит и весь отрезок, соединяющий эти точки.
Пусть

n
M
R
–
выпуклое множество. Точка

0
X
M
называется
крайней (экстремальной) точкой множества
M
, если из условия







0 1
2 1
X
X
X
,

1 2
,
X X
M ,


  0,1
следует, что


0 1
2
X
X
X
Выпуклой линейной комбинацией точек


1
,
,
r
n
X
X
R
называется точка, которую можно представить в виде:











1 1
;
0;
1, ;
1
r
r
i
i
i
i
i
i
X
X
i
r
Выпуклым
многогранником
M
, порожденным точками


1
,
,
r
n
X
X
R ,
называется множество всевозможных выпуклых линей- ных комбинаций точек

1
,
,
r
X
X :



















1 1
;
0;
1, ;
1
r
r
n
i
i
i
i
i
i
M
X
R X
X
i
r
Конечным конусом
K
,
порожденным векторами


1
,
,
r
n
A
A
R
, назы- вается множество всех векторов

n
X
R
, удовлетворяющих условию:











1 1
;
0;
1, ;
1
r
r
i
i
i
i
i
i
X
A
i
r
Рассмотрим систему нестрогих линейных неравенств (2.2.2) или (2.2.4).
Каждое линейное ограничение типа неравенства задает в
n
R
от- рицательное (положительное) полупространство









1 1
i
i
in
n
i
X a x
a x
b
(









1 1
i
i
in
n
i
X a x
a x
b ), ограниченное гиперплоскостью








1 1
i
i
in
n
i
X a x
a x
b .

9
Множество векторов, удовлетворяющих системе (2.2.2) или (2.2.4), можно представить как пересечение

m
n
полупространств:






1
m n
i
i
M
(






1
m n
i
i
M
).
Такое множество
M
называется многогранным множест-
вом.
Теорема 2.3.1 (о геометрической структуре множества допус-
тимых решений в задаче ЛП).
Множество
M
допустимых решений задачи линейного программи- рования можно представить в виде:


0
M
M
K
, где
0
M
– выпуклый многогранник, порожденный крайними точками мно- жества
M
;
K
–
конечный конус.
§ 2.4.
Геометрический метод решения задачи ЛП
Геометрический (графический) метод применим только для задач малой размерности (количество переменных в задаче равно 2 или 3), по- скольку он основан на геометрическом построении множества допусти- мых решений в задаче ЛП.
Рассмотрим геометрический метод решения задачи ЛП на несколь- ких примерах.
Пример 2.4.1.
Решим графически задачу из примера 2.1.1:








1 2
1 2
1 2
1 2
max max 5 3 ,
4;
5 2
10;
0,
0.
z
x
x
x
x
x
x
x
x
 
 
 
1 2
3
Геометрический метод реализуется в два этапа:
 построение допустимого множества решений задачи ЛП;
 нахождение оптимального решения среди всех допустимых.
Первому ограничению задачи соответствует прямая


1 2
4
x
x
, обо- значенная на рис. 2.4.1 значком
 
1
. Точки пересечения этой прямой с осями координат:

 

4,0 , 0,4
. Прямая


1 2
5 2
10
x
x
, соответствующая второму ограничению,
пересекается с осями координат в точках

 

2,0 , 0,5
Аналогичным образом учитываем ограничения
 
3
на знак переменных. Множество допустимых решений данной задачи изображе- но на рис. 2.4.1 в виде заштрихованного четырехугольника.

10
Рис. 2.4.1
Нахождение оптимального решения требует определения направ- ления наискорейшего роста целевой функции z . Такое направление за- дается градиентом целевой функции:






 





1 2
1 2
grad
,
,
z
z
z x x
x
x
Так как


1 2
5 3
z
x
x , то направление наискорейшего роста функции
z
определяется вектором




5,3
c
Вектор




5,3
c
также является век- тором нормали к линии уровня целевой функции



1 2
5 3
const
z
x
x
Точка пересечения области допустимых решений и прямой, соот- ветствующей максимальному значению целевой функции, и будет реше- нием задачи ЛП.
На рис. 2.4.1 видно, что это точка является точкой пересечения прямых (1) и (2). Ее координаты можно найти как решение системы уравнений, задающих эти прямые:

















*
*
*
1 2
1
*
*
*
1 2
2 4
2 3 5
2 10 10 3
x
x
x
x
x
x
Таким образом,

 (2 / 3,10 / 3)
X
– оптимальное решение;
 


 

*
5 2 3 3 10 / 3 40 / 3
z X
– максимальное значение целевой функции.
Пример 2.4.2. Решим геометрически задачу из примера 2.1.2:




1 2
min min 0,3 0,9
z
x
x
при ограничениях

11








1 2
1 2
1 2
1 2
800;
0,21 0,3 0;
0,03 0,01 0;
0,
0.
x
x
x
x
x
x
x
x
 
 
 
1 2
3
Постоим множество допустимых решений как пересечение полу- плоскостей, соответствующих трем ограничениям задачи. Заметим, что получившееся множество неограничено (рис.2.4.2) .
Рис. 2.4.2
Поскольку в данной задаче требуется найти минимум целевой функции


1 2
0,3 0,9
z
x
x ,
нас будет интересовать точка пересечения множества допустимых решений с линией уровня целевой функции, со- ответствующей минимально возможному значению z . Такой точкой яв- ляется точка пересечения прямых
 
1
и
 
2
. Чтобы найти координаты оп- тимальной точки
*
X
, решим систему уравнений:









*
*
1 2
*
*
1 2
800,
0,21 0,3 0
x
x
x
x








*
1
*
2 470,6 329,4
x
x
При данных значениях переменных минимальная стоимость пище- вой добавки составляет
 



*
*
*
1 2
0,3 0,9 437,64
z X
x
x
Пример 2.4.3. Решим геометрически задачу из примера 2.1.3.




1 2
max max 300 200
z
x
x
при ограничениях

12






1 2
1 2
1 2
3 2
120;
50;
0,
0.
x
x
x
x
x
x
 
 
 
1 2
3
Множество допустимых решений задачи приведено на рис. 2.4.3 и представляет собой заштрихованный четырехугольник. Поскольку вектор коэффициентов целевой функции




300,200
c
задает то же направле- ние, что и вектор коэффициентов первого ограничения


3,2
, любая точ- ка отрезка
AB
является оптимальной. В качестве оптимального решения можно взять либо точку


20,30
A
, либо точку


40,0
B
, либо любую точку на отрезке
AB
Максимальную прибыль компании можно найти так:
 
 



*
300 * 40 1200
z X
z B
Рис. 2.4.3
Пример 2.4.4. Добавим в предыдущую задачу еще два ограничения


1 2
30,
20
x
x
,
тогда задача будет иметь вид




1 2
max max 300 200
z
x
x
при ограничениях








1 2
1 2
1 2
1 2
3 2
120;
50;
30;
20;
0,
0.
x
x
x
x
x
x
x
x
 
 
 
 
 
1 2
3 4
5

13
Как видно из рис. 2.4.4 множество допустимых решений пусто, по- этому задача не имеет и оптимального решения.
Рис. 2.4.4
Пример 2.4.5. Решить задачу




1 2
max max 2
z
x
x
при ограничениях






1 2
1 2
1 2
1;
2 6;
0,
0.
x
x
x
x
x
x
 
 
 
1 2
3
Множество допустимых решений этой задачи неограничено (рис.
2.4.5)
. Градиент целевой функции:





2, 1
c
. При «движении» линии уровня в направлении градиента целевая функция неограниченно воз- растает, как следствие, задача не имеет оптимального решения. Отме- тим, что ограничение

1 0
x
в данной задаче ЛП является избыточным.
Рис. 2.4.5

14
Далее сформулируем общий алгоритм геометрического (графиче- ского) метода нахождения оптимального решения задачи ЛП.
Экстремальной точкой в задаче ЛП будем называть крайнюю (уг- ловую) точку множества допустимых решений.
Теорема 2.4.1. (об оптимальных экстремальных точках).
Если в задаче ЛП существует оптимальное решение, то существует и оптимальная экстремальная точка.
Алгоритм графического метода решения задач ЛП с двумя пе-
ременными:
 записать каждое ограничение задачи ЛП как равенство (уравнение) и нарисовать соответствующую прямую в координатной плоскости;
 для каждого ограничения (неравенства) определить (нарисовать) допустимую область, а затем допустимую область для всех ограничений
(она представляет собой пересечение таких областей для всех ограничений). Полученная область представляет собой множество допустимых решений задачи ЛП;
 записать уравнение линии уровня целевой функции:



1 2
,
const
z x x
;
 найти градиент целевой функции






 





1 2
1 2
grad
,
,
z
z
z x x
x
x
, который показывает направление наискорейшего роста функции z . «Сдвигать» линию уровня целевой функции в направлении градиента (в случае на- хождения максимума) или в направлении, противоположном градиенту (в случае нахождения минимума);
 экстремальная (угловая) точка, которая лежит на пересечении «по- следней» линии уровня целевой функции и множества допустимых решений, и будет оптимальным решением задачи ЛП;
 чтобы аналитически найти координаты оптимальной точки, состав- ляем систему уравнений из ограничений, соответствующих прямым, про- ходящим через эту точку. Вычислить значение целевой функции в оптимальной точке (значение задачи ЛП).
При решении задачи ЛП возможны следующие случаи:
1.
Задача ЛП имеет единственное решение (см. примеры 2.4.1 и
2.4.2).
2.
Задача ЛП имеет бесконечное множество решений (пример 2.4.3), это возможно, если линия уровня целевой функции параллельна прямой, соответствующей одному из ограничений задачи.
3.
Задача ЛП не имеет оптимального решения, это является либо следствием неограниченности множества допустимых решений (пример
2.4.5
), либо следствием его пустоты (пример 2.4.4).

15
§2.5
. Анализ оптимального решения на чувствительность
Модель линейного программирования является как бы
«моментальным снимком» реальной ситуации, когда параметры модели предполагаются неизменными. Естественно изучить влияние изменения параметров модели на полученное оптимальное решение задачи ЛП.
Такое исследование оптимального решения называется анализом на
чувствительность.
Пример 2.5.1. Проведем анализ на чувствительность оптимально- го решения, найденного в примере 2.4.1.
Напомним, что оптимальное решение рассматриваемой задачи вектор

 (2 / 3,10 / 3)
X
и

 40 / 3.
z
Первая задача анализа на чувствительность – чувствительность к правой части ограничений. В рамках этой задачи ограничения классифицируются как:
 связывающие (активные), если соответствующие им прямые проходят через оптимальную точку;
 несвязывающие (неактивные), если соответствующие им прямые не проходят через оптимальную точку.
Связывающим (активным) ограничениям отвечают дефицитные
ресурсы, т. е. ресурсы, используемые полностью. Несвязывающим (неак- тивным) ограничениям отвечают недефицитные ресурсы.
Цели первой задачи на чувствительность:
 определить предельно допустимое увеличение запаса дефицитно- го ресурса, позволяющее улучшить найденное значение целевой функ- ции;
 определить предельно допустимое снижение запаса недефицитно- го ресурса, не изменяющее найденного оптимального решения.
Ресурс 1 – дефицитный, ограничение (1) – связывающее (активное);
Ресурс 2 – дефицитный, ограничение (2) – связывающее (активное).
Рис. 2.5.1

16
Для ресурса 1 предельно допустимое увеличение запаса состав- ляет 1 единицу (с 4 до 5 единиц), т. к. прямую (1) имеет смысл двигать параллельно себе до точки (0,5), ей будет отвечать уравнение
 

1
:


1 2
5
x
x
. Максимальная прибыль будет в точке с координатами (5,0), z(0,5)=15 и увеличится на


15 40 3 5 3
(рис. 2.5.1).
При увеличении запаса второго дефицитного ресурса, прямую (2) следует двигать до точки (4,0), такому положению прямой соответствует уравнение


1 2
5 2
20
x
x
, и изменение запаса второго ресурса равно 10.
Максимальная прибыль z(4,0)=20, изменение прибыли при изменении запаса второго ресурса равно


20 40 3 20 3
(рис. 2.5.2).
Рис. 2.5.2
Результаты решения первой задачи анализа на чувствительность оформляются в виде таблицы:
Ресурс
Тип (статус) ресурса
Максимальное изменение запаса
Максимальное из- менение дохода
Ресурс(1) дефицитный


5 4
1


15 40 3 5 3
Ресурс(2) дефицитный


20 10 10


20 40 3 20 3
Вторая задача анализа на чувствительность позволяет опреде- лить меру зависимости оптимального решения от изменения ограниче- ний, накладываемых на ресурсы. Эта мера называется теневой (двой-
ственной) ценой ресурса и показывает, на сколько изменится оптималь- ное значение целевой функции при изменении количества ресурса на единицу.
Теневая (двойственная) цена ресурса
i
обозначается
i
y
и вычис- ляется по формуле:

17

Максимальное увеличение дохода
Максимальное увеличение запаса -го ресурса
i
y
i
Для рассматриваемой задачи


1 15- 40 3 5
1 3
y
,


2 20- 40 3 2
20 3
y
Заметим, что для недефицитных ресурсов теневая цена всегда равна нулю. Можно сделать вывод, что наиболее выгодно увеличение первого ресурса, т. к. прибыль на единицу этого ресурса больше.
Третья задача анализа на чувствительность состоит в опреде- лении пределов изменения коэффициентов целевой функции, позво- ляющих сохранить оптимальное решение задачи.
Пусть


1 1 2
2
z
c x
c x –
целевая функция,


11 1 12 2
1
a x
a x
b и


21 1 22 2
2
a x
a x
b – два активных ограничения в оптимальной точке
*
X
(рис. 2.5.3). При изменении коэффициентов целевой функции решение остается оптимальным, если соотношение коэффициентов
1 2
c
c
удовле- творяет неравенству


11 1
21 12 2
22
a
c
a
a
c
a
(диапазон оптимальности).
В рассматриваемом примере решение

 (2 / 3,10 / 3),
X
остается оптимальным, если


1 2
1 5
1 2
c
c
Рис. 2.5.3
В частности, если


1
const
5
c
,


2 1
5 5
1 2
c
, 

2 2
5
c
;

18 если


2
const
3
c
, 

1 1
5 1
3 2
c
,


1 15 3
2
c
Выводы
 Многие проблемные ситуации могут быть сформулированы как за- дачи ЛП, если они удовлетворяют следующим математическим предпо- ложениям: определенности, линейности, делимости.
 Структурными составляющими задачи ЛП являются: переменные, целевая функция, ограничения и ограничения на знак переменных.
 Оптимальное решение для задач малой размерности может быть получено с помощью геометрического метода.
 Геометрически оптимальное решение задачи ЛП находится на гра- нице множества допустимых решений.
 Задача ЛП может иметь одно оптимальное решение, бесконечное множество оптимальных решений или не иметь оптимальных решений.
 Анализ на чувствительность выявляет зависимость оптимального решения от возможных изменений параметров исходной модели.
Вопросы для самопроверки
1.
Назовите основные предположения, которым должна удовлетво- рять модель ЛП.
2.
Назовите основные этапы формализации задачи ЛП.
3.
Сформулируйте проблему, которую можно формализовать как за- дачу ЛП.
4.
Дайте определение задачи ЛП.
5.
Дайте определение допустимого решения задачи ЛП и допустимого множества решений задачи ЛП.
6.
Что понимают под оптимальным решением задачи ЛП?
7.
Дайте определение выпуклого множества.
8.
Что такое крайняя (экстремальная) точка множества?
9.
Какую структуру имеет множество допустимых решений задачи ЛП?
10.
Сформулируйте алгоритм геометрического метода решения зада- чи ЛП.
11.
В чем отличие решения задачи ЛП максимизации от задачи ЛП минимизации при геометрическом методе?
12.
Сколько решений может иметь задача ЛП?
13.
В чем сущность анализа оптимального решения на чувствитель- ность?
14.
Дайте определение активного (связывающего) ограничения.
15.
Что такое дефицитный ресурс?
16.
Что понимают под теневой (двойственной) ценой ресурса?
17.
Чему равна теневая цена недефицитного ресурса?

19 18.
Можно ли улучшить значение целевой функции, изменяя запас недефицитного ресурса?
19.
Всегда ли изменение коэффициентов целевой функции приводит к изменению оптимального решения задачи ЛП?
Библиография
1.
Таха Х.А. Введение в исследование операций. 7-е изд. М.: Изд. дом
«Вильямс», 2005.
2.
Ху Т. Целочисленное программирование и потоки в сетях.М.: Мир,
1972.
3.
Зайченко Ю.П. Исследование операций. 2-изд. Киев: Изд-во «Вища школа», 1979.
4.
Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. М.: Дело, 2003.
5.
Зенкевич Н.А., Марченко И.В. Экономико-математические методы.
Рабочая тетрадь №2. СПб.: изд-во МБИ, 2005.
6.
Хазанова Л.Э. Математическое моделирование в экономике. М.:
Изд-во БЕК, 1998.
7. Cook
Т. & Russel R.A. Introduction to Management Science. Engle- wood Cliffs (New Jersey), Prentice Hall, Inc. 1989.
8. Winston W.L. Introduction to Mathematical Programming: Applications and Algorithms. Boston (Mass.): PWS-KENT Publ., 1991.
9. Winston W.L. Operations Research: Applications and Algorithms. Bos- ton (Mass.): PWS-KENT Publ., 1990.