ВУЗ:
Составители:
Рубрика:
Для решения задач методами линейного программирования необходимо, чтобы модель задачи удовлетворяла следую-
щим условиям.
1. Задача должна быть связана с ограниченными ресурсами,
например, ограниченное количество оборудования, време-
ни и т.п.
2. Требуется четкая формулировка критерия оптимальности, обычно это максимизация прибыли или минимизация за-
трат.
3. Задача должна характеризоваться линейностью
функции цели и ограничений.
4. В задаче должна соблюдаться однородность
используемых переменных и параметров, например, изделия, изготов-
ляемые на станке, идентичны; затраты времени, в течение которых выполняются операции, используются с одинаковой про-
дуктивностью и т.д.
5. Варьируемые переменные и ресурсы должны быть делимы,
т.е. их можно разделять на доли. Если такое деление не-
возможно, то используется модификация метода линейного программирования – дискретное
(или целочисленное) програм-
мирование.
Формально модель задачи линейного программирования имеет следующий вид. Например, рассматривается задача оп-
тимизации, заключающаяся в том, чтобы определить значения неотрицательных варьируемых переменных
(
)
n
xxxx ...,,,
21
=
, при которых целевая функция
nnn
xxxxcxcxcQ ,...,,extr...
212211
→+++=
(4.1)
принимает экстремальное (максимальное или минимальное) значение, выполняются ограничения на разного рода ресурсы:
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
≤+++
≤+++
≤+++
...
.......................................................
;...
;...
2211
22222121
1121211
(4.2)
и
условие
,,1,0 nix
i
=≥
(4.3)
где
−== ),1;,1(,, mjnibac
jiji
заданные
постоянные
величины
(
параметры
).
В
задаче
(4.1) – (4.3)
целевая
функция
Q
представляет
собой
линейную
форму
,
а
ограничения
в
виде
линейных
нера
-
венств
или
равенств
задают
область
допустимых
решений
задачи
.
Вследствие
линейности
ограничений
допустимая
область
представляет
собой
выпуклый
многоугольник
(
симплекс
).
Основная
идея
метода
заключается
в
направленном
переборе
вер
-
шин
симплекса
с
целью
определения
вершины
,
в
которой
целевая
функция
(4.1)
принимает
экстремальное
значение
.
Если
2
=
n
,
то
определение
вершины
многоугольника
,
соответствующей
экстремальному
значению
Q
,
легко
показать
графически
.
Пример 4.1
.
Пусть
решается
задача
максимизации
прибыли
предприятия
,
представленная
следующей
моделью
:
;max42
21
,
21
xx
xxQ →+=
(4.4)
;12064
21
≤+ xx
(4.5)
;7262
21
≤+ xx
(4.6)
;10
2
≤x
(4.7)
.0,
21
≥xx
(4.8)
Здесь
переменные
и
параметры
имеют
следующий
смысл
:
−
21
, xx
количества
изделий
первого
и
второго
видов
соот
-
ветственно
,
выпускаемых
предприятием
;
−== 4,2
21
cc
прибыли
,
которые
приносит
одно
изделие
соответственно
первого
и
второго
вида
;
−
Q
прибыль
предприятия
от
выпускаемых
изделий
;
−=== 10,72,120
321
bbb
производственные
мощности
(
например
,
в
единицах
времени
)
трех
участков
,
на
которых
изготовляются
изделия
;
−== 6,4
1211
aa
затраты
времени
на
пер
-
вом
участке
для
соответствующих
изделий
;
−== 6,2
2221
aa
аналогично
на
втором
участке
;
−== 1,0
3231
aa
на
третьем
.
Таким
образом
,
требуется
определить
,
сколько
надо
выпускать
изделий
первого
(
)
1
x
и
второго
(
)
2
x
видов
,
чтобы
при
-
быль
предприятия
была
максимальна
.
На
рис
. 4.8
показана
допустимая
область
,
ограниченная
линиями
,
которые
получаются
из
(4.5) – (4.8)
в
результате
заме
-
ны
знаков
неравенств
≥
≤
и
на
равенства
(
)
=
.
Полученный
многоугольник
имеет
пять
вершин
,
на
рисунке
они
обозначены
кружками
.
Пунктиром
здесь
обозначены
линии
равных
значению
Q
(4.4).
Прибыль
возрастает
,
если
линия
21
42 xxQ +=
переме
-
щается
(
парал
-
Страницы
- « первая
- ‹ предыдущая
- …
- 128
- 129
- 130
- 131
- 132
- …
- следующая ›
- последняя »
