Отправляет email-рассылки с помощью сервиса Sendsay

Математика управления капиталом

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Секреты инвестирования" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Июнь 2006   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Сергей Спирин

Статистика

2.119 подписчиков
-4 за неделю
←   Все выпуски   →

Математика для экономистов Выпуск от 25.


 

 

Математика для экономистов

 

 

 

Алгебраическое представление линейных оптимизационных моделей

 

Часть 1

 

 

Математические представления, сформулированные для ряда моделей в прошлых выпусках, можно обобщить следующим образом. Пусть xj есть j-я управляемая переменная (j = 1, 2, :, n). Требуется определить такие значения xj, чтобы выражение

p1x1 + p2x2 + : pnxn

в зависимости от содержания задачи было максимизировано или минимизировано. На xj наложен ряд ограничений, каждое из которых относится к одному из следующих типов:

a1x1 + a2x2 + : anxn ≥ a,

b1x1 + b2x2 + : bnxn = b,

c1x1 + c2x2 + : cnxn ≤ c.

Кроме того, может иметь место ограничение xj ≥ 0.

Задача оптимизации при такого вида ограничениях:

1) может не иметь ни одного допустимого решения, т.е. может не существовать таких значений переменных xj (j = 1, 2, :, n), которые удовлетворяли бы всем ограничениям;

2) может иметь единственное допустимое оптимальное решение;

3) может иметь несколько допустимых оптимальных решений;

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

Переход от максимизации к минимизации. В ЛП любая задача максимизации может быть сведена к эквивалентной задаче минимизации (и наоборот), если одновременно с изменением "знака" оптимизации произвести изменение знаков перед всеми коэффициентами в выражении для целевой функции. Так, например, максимизация Σ cjxj эквивалентна минимизации Σ (-cj)xj. Если при этом V - оптимальное значение линейной формы Σ (-cj)xj, то -V представляет собой оптимальное значение линейной формы Σ cjxj.

Переход к эквивалентной системе неравенств. Каждое из неравенств, фигурирующих в модели ЛП, можно записать в инверсивной форме, если учесть, что

Σ аjxj ≤ b эквивалентно Σ (-aj)xj ≥ -b.

Так, например, неравенство

1x1 - 1x2 ≤ -4 эквивалентно неравенству

-1x1 + 1x2 ≥ 4.

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

Σ аjxj ≤ b можно записать в виде Σ аjxj + 1s = b, где s ≥ 0,

Σ аjxj ≥ b можно записать в виде Σ аjxj - 1t = b, где t ≥ 0.

Переменную типа s принято называть остаточной переменной, а переменную типа t обычно называют избыточной переменной.

Так, например, в задаче распределения ресурсов, рассмотренной в прошлых выпусках рассылки, ограничение на количество имеющегося в наличии материала Y имело вид:

7x1 + 5x2 + 3x3 + 2x4 ≤ 120.

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

7x1 + 5x2 + 3x3 + 2x4 + 1y = 120, где y ≥ 0.

Здесь y интерпретируется как остаток (или неиспользованная часть) материала Y.

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

2x1 + 3x2 + 7x3 - 1а = 1250, где а ≥ 0.

В этом случае а интерпретируется как мера превышения потребности в ингредиенте А.

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

Например, как нетрудно проверить графически, система уравнений х = 1, у = 2 эквивалентна комбинации неравенств х ≤ 1, у ≤ 2, х + у ≥ 3, которую в свою очередь можно представить в виде х ≤ 1, у ≤ 2, - х - у ≤ -3.

Изложенное выше допускает следующее обобщение:

систему уравнений Σ аijxj = bi (i =1, 2, :, m)

можно записать в виде

Σ аijxj ≤ bi (i =1, 2, :, m), Σ αjxj = β,

где

αj = - Σ аij, β = - Σ bi.

Таким образом, при m = 1 соотношения сводятся к

Σ а1jxj ≤ b1, - Σ а1jxj ≤ b1.

В качестве примера рассмотрим систему уравнений

1x1 + 1x2 = 1,

2x1 - 4x3 = -5.

Эта система эквивалентна следующей системе неравенств:

1x1 + 1x2 ≤ 1,

2x1 - 4x3 ≤ -5,

- 3x1 - 1x2 + 4x3 ≤ 4.

В следующем выпуске рассылки:

        переход от переменных, не имеющих ограничения в знаке, к неотрицательным переменным;

        переход от переменных, значения которых ограничены снизу, к неотрицательным переменным.

 

 

 

 

 

 

 

 

 

 

mathematics.economics@rambler.ru

Автор оставляет за собой право:

а) отвечать не на все полученные письма,
б) публиковать полностью или частично полученные письма в рассылке.

 

 

 
В избранное