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

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

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

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

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

←   Январь 2004   →
 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
31
Автор
Сергей Спирин

Статистика

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

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


Информационный Канал Subscribe.Ru

Математика для экономистов.
Выпуск #13. E-mail: mathematician@home.tula.net URL: http://mathematics.boom.ru
СИМПЛЕКСНЫЙ МЕТОД
Часть 1

Общая постановка задачи

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования, записанную в каноническом виде.

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

Алгоритм симплексного метода

1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки /\j (индексная строка), заполняем по данным системы ограничений и целевой функции).

ci БП c1 c2 ... cm cm+1 ... cn L(x*)
x1 x2 ... xm xm+1 ... xn bi
c1 x1 1 0 ... 0 h1,m+1 ... h1n f1
c2 x2 0 1 ... 0 h2,m+1 ... h2n f2
... ... ... ... ... ... ... ... ... ...
cm xm 0 0 ... 1 hm,m+1 ... hmn fm
/\j 0 0 ... 0 /\m+1 ... /\n L(x1*)

Индексная строка для переменных находится по формуле

/\j = (с1h1j + с2h2j + ... + сmhmj) - cj, j = 1,2,...,n

и по формуле

/\j = с1f1 + с2f2 + ... + сmfm для свободного члена.

Возможны следующие случаи при решении задач на максимум:

  • если все оценки /\j > 0, то найденное решение оптимальное;
  • если хотя бы одна оценка /\j < 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращаем, так как целевая функция L(x*) неограничена в области допустимых решений;
  • если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;
  • если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

Если хотя бы одна оценка /\k < 0, то k-ый столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

3. Заполняем симплексную таблицу 2-го шага:

  • переписываем ключевую строку, разделив ее на ключевой элемент;
  • заполняем базисные столбцы;
  • остальные коэффициенты таблицы заполняем по правилу "прямоугольника". Так же считаем и оценки. Получаем новое опорное решение, которое проверяем на оптимальность и т.д.

Правило "прямоугольника" заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h1,m+1. Тогда элемент i-й строки (m+2)-го столбца 2-го шага - обозначим его h'i,m+2 - согласно правилу "прямоугольника" выражается формулой

h'i,m+2 = (h1,m+1 * hi,m+2 - hi,m+1 * h1,m+2) / h1,m+1

где hi,m+2, hi,m+1, h1,m+1 - элементы 1-го шага.

Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок /\j при всех j = 1,2,...,n.

Анализ эффективности использования производственного потенциала предприятия

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

Производственные ресурсы Расход ресурсов за 1 месяц при работе Общий ресурс
1-м способом 2-м способом
Сырье 1 2 4
Оборудование 1 1 3
Электроэнергия 2 1 8

При первом способе производства предприятие выпускает за один месяц 3 тыс. изделий, при втором - 4 тыс. изделий.

Сколько месяцев должно работать предприятие каждым из этих способов, чтобы при наличных ресурсах обеспечить максимальный выпуск продукции?

РЕШЕНИЕ. Составим математическую модель задачи. Обозначим: x1 - время работы предприятия первым способом, x2 - время работы предприятия вторым способом.

Математическая модель имеет вид

L(x*) = 3x1 + 4x2 --> max

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

{x1 + 2x2 < 4,
{x1 + x2 < 3,
{2x1 + x2 < 8,

x1 > 0, x2 > 0.

Приведем задачу к каноническому виду:

L(x*) = 3x1 + 4x2 --> max

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

{x1 + 2x2 + x3 = 4,
{x1 + x2 + x4 = 3,
{2x1 + x2 + x5 = 8,

xj > 0, j = 1,2,3,4,5.

Составим симплексную таблицу 1-го шага.

ci БП 3 4 0 0 0 L(x*)
x1 x2 x3 x4 x5 bi
0 x3 1 2 1 0 0 4
0 x4 1 1 0 1 0 3
0 x5 1 1 0 0 1 8
/\j -3 -4 0 0 0 0

Получим решение:

X*1 = (0,0,4,3,8), L(x*1) = 0.

В индексной строке /\j имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить. В качестве ключевого столбца следует принять столбец базисной переменной x2, а за ключевую строку взять строку переменной x3, где min(4/2,3/1,8/1) = min(2,3,8) = 2.

Ключевым элементом является 2. Вводим в столбец базисной переменной x2, выводим x3. Составляем симплексную таблицу 2-го шага.

ci БП 3 4 0 0 0 L(x*)
x1 x2 x3 x4 x5 bi
4 x2 1/2 1 1/2 0 0 2
0 x4 1/2 0 -1/2 1 0 1
0 x5 3/2 0 -1/2 1 1 6
/\j -1 0 2 0 0 8

Получим

X*2 = (0,2,0,1,6), L(x*2) = 8.

В индексной строке имеется одна отрицательная оценка. Полученное решение можно улучшить. Ключевым элементом является 1/2. Составляем симплексную таблицу 3-го шага.

ci БП 3 4 0 0 0 L(x*)
x1 x2 x3 x4 x5 bi
4 x2 0 1 1 -1 0 1
3 x1 1 0 -1 2 0 2
0 x5 0 0 1 -3 1 3
/\j 0 0 1 2 0 10

Все оценки свободных переменных /\j > 0, следовательно, найденное опорное решение является оптимальным:

X*опт = (2,1,0,0,3), L(x*max) = 10.

Таким образом, по первому способу предприятие должно работать два месяца, по второму - один месяц, при этом максимальный выпуск продукции составит 10 тыс. ед.

Альтернативный оптимум

При решении задач ЛП симплексным методом критерием оптимальности является условие /\j > 0 для задач на максимум и условие /\j < 0 для задач на минимум. Если на каком-то шаге окажется, что хотя бы одна оценка свободной переменной /\j = 0, а все остальные /\j > 0 для задач на максимум ( /\j < 0 для задач на минимум), то, приняв в качестве ключевого столбца столбец, где /\j = 0, и найдя новое оптимальное решение, заметим, что значение целевой функции при этом не изменится. В этом случае задача имеет альтернативный оптимум.

Критерием альтернативного оптимума при решении задач симплексным методом является равенство нулю хотя бы одной оценки свободной переменной (/\j = 0).

Если только одна оценка свободной переменной равна нулю, то решение находится по формуле

X*опт = tX*опт1 + (1 - t)X*опт2, где 0 <t<1.

Если две оценки и более, например S, свободных переменных равны нулю, то оптимальное решение определяется по формуле

X*опт = t1X*1 + t2X*2 + ... + tsX*s, где t1 + t2 + ... + ts = 1, ti>0.

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

ПРИМЕР. Дана задача ЛП

L(x*) = 2x1 - 4x3 + 5x5--> min

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

{x1 + 3x2 - x3 + 2x5 = 7,
{-x2 + 4x3 + x4 = 12,

xj > 0, j = 1,2,3,4,5.

РЕШЕНИЕ. Составим симплексную таблицу.

ci БП 0 2 -4 0 2 L(x*)
x1 x2 x3 x4 x5 bi
0 x1 1 3 -1 0 2 7
0 x4 0 -2 4 1 2 12
/\j 0 -2 4 0 0 10

В индексной строке имеется одна положительная оценка. Полученое решение можно улучшить. Ключевым элементом является 4. Составим симплексную таблицу 2-го шага.

ci БП 0 2 -4 0 2 L(x*)
x1 x2 x3 x4 x5 bi
0 x1 1 5/2 0 1/4 2 10
-4 x3 0 -1/2 1 1/4 1/2 3
/\j 0 0 0 -1 -2 -12

Получаем

X*опт1 = (10,0,3,0,0).

Так как /\2 = 0, то задача имеет альтернативный оптимум. Найдем еще одно оптимальное решение, введя вместо базисной переменной x1 свободную переменную x2.

ci БП 0 2 -4 0 2 L(x*)
x1 x2 x3 x4 x5 bi
2 x2 2/5 1 0 1/10 4/5 4
-4 x3 1/5 0 1 3/10 9/10 5
/\j 0 0 0 -1 -4 -12

Получаем

X*опт2 = (0,4,5,0,0).

Найдем координаты оптимального решения задачи:

x1 = 10t + (1-t)0 = 10t,
x2 = 0t + (1-t)4 = 4 - 4t,
x3 = 3t + (1-t)5 = -2t + 5,
x4 = 0t + (1-t)0 = 0,
x5 = 0t + (1-t)0 = 0.
X*опт = (10t, 4-4t, 5-2t, 0, 0).

Давая t значения из [0,1], получим различные X*опт, при которых L(x*) = -12.
MATHCAD

n-мерное векторное пространство действительных чисел

Координаты вектора вводятся на рабочем листе Mathcad-документа следующим образом. Пусть, к примеру, надо ввести вектор vect1= (3, 2, 5.6, -8). Разместите курсор (красный крестик) в нужном месте рабочего листа. Введите имя вектора vect1. Клавишей <:> введите знак присваивания :=. Комбинацией клавиш <Ctr>+<M> введите диалоговое окно Вставить матрицу (Insert Matrix). В поле Строк (Rows) этого окна задайте размерность вектора 4. В поле Колонок (Columns) задайте 1. Щелкните на кнопке ОК. Справа от знака присваивания (на месте метки, выделенной синим курсором ввода) появится шаблон вектора для ввода его координат.

Некоторые операции над векторами производятся с помощью подпанели инструментов Матрица (Matrix) понели инструментов Математика (Math). Подпанель Матрица (Matrix) содержит 12 кнопок. Щелкнув на кнопке скалярного произведения, можно вывести шаблон и на месте меток ввести векторы, участвующие в скалярном произведении. Можно воспользоваться также кнопкой, которая задает шаблон для определения суммы координат вектора, имя которого следует задать на месте метки.

Задача.

Даны векторы x и y одинаковой размерности, i-я координата вектора x - это размер в млн. ден. ед. креита, выданного банком i-й фирме, i-я координата вектора y - годовая процентная ставка этого кредита. Определить общую сумму кредита; прибыль, которую банк должен получить по истечении года за кредиты, выданные фирмам; процент прибыли от общей суммы кредитов.

х = (1.5, 5.2, 11, 0.7, 3.2, 33.5, 8.5, 6.3);

у = (3.8, 4.5, 1.7, 6, 4.7, 12, 22.3, 17.3).

Решение.

Искомая прибыль будет равна скалярному произведению векторов х и у, деленному на 100. Поэтому для решения этой задачи с помощью Mathcad необходимо выполнить следующие действия. Ввести координаты векторов х и у. Определить суммарную величину кредита: kr:=[сумма]x. Определить прибыль банка pr:=[xy]/100. Процент прибыли от общей суммы кредита будет равен (pr/kr)/100.

Содержание рассылки зависит и от Вас: чем активнее Вы проявляете свою заинтересованность в той или иной теме, задаете те или иные вопросы - тем полезнее рассылка будет для каждого из Вас! Пишите: mathematician@home.tula.net.
http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное