ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.02.2026
Просмотров: 233
Скачиваний: 2
план использования средств, если доход от выданных кредитов составляет в среднем - 20%, а от ценных бумаг – 10%.
Экономико-математическая модель задачи:
Предположим, x1, x2 средства банка размещенные
соответственно в кредитах и ценных бумагах. Тогда получим следующую задач линейного программирования:
Найти максимум линейной целевой функции – функции дохода
Z = 0,2 × x1 + 0,1× x2 ® max
при заданных ограничениях по свободным средствам, по
объему выдаваемых кредитов и по стратегии банка
ìx1 + x2 £ 120 ïïx1 ³ 30
íïx2 ³ 0,4(x1 + x2 )
ïîx1, x2 ³ 0
Таким образом, задача определения стратегии банка так же, как и задача использования ресурсов, сводится к стандартной задаче линейного программирования.
2. Общая, стандартная и основная задачи линейного программирования
О п р е д е л ен и е 1 . Общей задачей ЛП называется задача нахождения максимального (минимального) значения
линейной целевой функции
n
z = å c j x j ® min(max) (1) при условиях
j=1
n |
|
|
|
|
|
|
|
|
|
å aij x j |
£³ bi , |
i = |
1, k |
|
|
(2) |
|||
j=1 |
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
å aij x j = bi , |
i = k +1, m |
(3) |
|||||||
j =1 |
|
|
|
|
|
|
|
|
|
x j ³ 0 , |
j = |
|
, |
l ≤ n |
(4), |
||||
1,l |
|||||||||
8
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
где aij , bi , c j - заданные постоянные величины и k £ m .
О п р е д е л ен и е . 2 . Функция Z называется целевой функцией задачи (1 - 4), x j - проектными параметрами задачи,
а условия (2 - 4) ограничениями данной задачи.
О п р е д е л ен и е |
3 . |
Стандартной задачей |
ЛП |
называется задача нахождения |
целевой функции (1) |
при |
|
выполнении условий (2), |
(4), |
где k=m, l=n, т.е. |
когда |
ограничения заданы только в виде неравенств (2), и все
проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде равенств отсутствуют:
n |
|
|
|
|
|
|
|
|
z = å c j x j ® min(max) |
|
|||||||
j=1 |
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
å aij x j |
£³ bi , |
i = |
1, m |
|
|
|||
j=1 |
|
|
|
|
|
|
|
|
x j ³ 0 |
, |
j = |
|
. |
|
|
|
|
1, n |
|
|
|
|
||||
О п р е д е л ен и е |
4 . Канонической |
(или основной) |
||||||
задачей ЛП |
называется |
задача нахождения |
максимального |
|||||
(минимального) значения функции (1) при выполнении условий (3), (4), где k=0, l=n, m<n, т.е. когда ограничения заданы только в виде равенств (3), и все проектные параметры удовлетворяют условиям неотрицательности (4), а условия в виде неравенств
(2) отсутствуют:
n |
|
|
|
||
z = å c j x j ® min(max) |
|||||
j=1 |
|
|
|
||
n |
|
|
|
||
åaij x j = bi , |
i = |
|
|
||
1, m |
|||||
j=1 |
|
|
|
||
x j ³ 0 , j = |
|
, |
m < n . |
||
1, n |
|||||
9
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
|
|
О п р е д е л ен и е 5 . Совокупность значений проектных |
||||||||||
параметров X = {x1, x2,..., xn}, |
удовлетворяющих ограничениям |
|||||||||||
задачи (2-4), называется допустимым решением, или планом. |
|
|||||||||||
|
|
О п р е д е л ен и е |
6 . |
План X * = {x*, x* |
,..., x*} , |
при |
||||||
|
|
|
|
|
|
|
|
|
1 |
2 |
n |
|
котором |
целевая |
функция |
(1) принимает |
свое |
максимальное |
|||||||
(минимальное) |
значение, |
|
называется |
оптимальным, |
т.е. |
|||||||
Z(X |
* |
) ³ |
æ |
|
* |
|
ö |
|
|
|
|
|
|
Z(X ) çZ(X |
|
) £ Z(X )÷ . |
|
|
|
|
|||||
|
|
|
è |
|
|
|
ø |
|
|
|
|
|
Все три формы задачи ЛП эквивалентны, ибо каждая из
них с помощью некоторых преобразований может быть переписана в форме другой задачи. При этом необходимо пользоваться следующими правилами:
1. Задачу минимизации функции можно свести к задаче максимизации, и, наоборот, путем замены знаков
коэффициентов |
c j |
на |
противоположные, |
поскольку |
min Z = - max(-Z) . |
|
|
|
|
2. Ограничения-неравенства (2) можно заменить эквивалентными ограничениями-равенствами путем введения
дополнительных неотрицательных переменных следующим образом:
n
Ограничение-неравенство вида å aij x j £ bi j =1
преобразуется |
|
в |
|
ограничение-равенство |
|||
n |
+ xn+1 |
= bi ,xn+1³ 0 , |
|
xn+1 ³ 0 , |
а |
ограничение- |
|
å aij x j |
|
||||||
j =1 |
|
|
|
|
|
|
|
неравенство вида |
n |
³ bi |
- в ограничение-равенство |
||||
å aij x j |
|||||||
|
|
|
j =1 |
|
|
|
|
n |
- xn+1 |
= bi |
, xn+1 ³ 0 . |
|
|
|
|
å aij x j |
|
|
|
||||
j=1 |
|
|
|
|
|
|
|
При этом число дополнительных переменных равно числу преобразуемых неравенств.
10
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com
Вводимые дополнительные переменные имеют вполне определенный смысл. Так, например, для задачи распределения
ресурсов числовое значение дополнительной переменной равно объему неиспользованного соответствующего ресурса. С
математической точки зрения основные и дополнительные переменные играют одинаковую роль. Поэтому целесообразно их единообразное обозначение.
4. Каждое ограничение-равенство вида (3) можно
|
|
|
n |
|
|
x |
|
£ b |
|
|
|
å a |
|
|
|||
записать в виде двух неравенств |
j=1 |
|
ij |
|
j |
i . |
||
|
|
|
n |
|
|
x |
|
³ b |
|
|
|
å a |
|
|
|||
|
|
|
j=1 |
|
ij |
|
j |
i |
5. |
Переменная |
x j , |
|
неограниченная условием |
||||
неотрицательности вида (4), можно заменить разностью двух дополнительных неотрицательных переменных: x j = x /j - x//j ,
x |
/ |
³ 0 , |
x |
// |
³ 0 . |
|
j |
|
|
j |
|
3. Геометрическая интерпретация задачи линейного программирования
Рассмотрим задачу, состоящую в определении максимального значения функции:
Z = c1x1 + c2 x2 ® max(min) (5) при условиях
ai1x1 + ai2 x2 £³ bi , |
i = |
1,m |
(6) |
x1 ³ 0 , x2 ³ 0 |
(7). |
||
Эта задача ЛП в стандартной форме с двумя переменными.
Каждое неравенство вида (6), (7) геометрически
определяет полуплоскость соответственно с граничными прямыми
ai1x1 + ai2 x2 = bi , i = |
1, m |
(8). |
x1 = 0, x2 = 0 |
|
|
11
PDF создан испытательной версией pdfFactory Pro www.pdffactory.com