Контрольная работа: Задачи линейного программирования. Алгоритм Флойда

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

1.Постановка задачи.

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

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

4.Решение задач, сформулированных на базе построенной математической модели.

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

6.Реализация полученного решения на практике.

Математическое моделирование в исследовании операций является, с одной стороны, очень важным и сложным, а с другой — практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах.

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

Управление портфелем активов. Рассмотрим проблему принятия инвестором решения о вложении имеющегося у него капитала. Набор характеристик потенциальных объектов для инвестирования, имеющих условные имена от А до F, задается следующей таблицей.

Название	Доходность (в %)	Срок выкупа (год)	Надежность (в баллах)
А	5,5	2001	5
В	6,0	2005	4
С	8,0	2010	2
D	7,5	2002	3
Е	5,5	2000	5
F	7,0	2003	4

Предположим, что при принятии решения о приобретении активов должны быть соблюдены условия:

a.суммарный объем капитала, который должен быть вложен, составляет $ 100 000;

b.доля средств, вложенная в один объект, не может превышать четверти от всего объема;

c.более половины всех средств должны быть вложены в долгосрочные активы (допустим, на рассматриваемый момент к таковым относятся активы со сроком погашения после 2004 г.);

d.доля активов, имеющих надежность менее чем 4 балла, не может превышать трети от суммарного объема.

Приступим к составлению экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как х_А , х_В , х_С , х_D , х_E , х_F . Тогда суммарная прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде

(1)

На следующем этапе моделирования мы должны формально описать перечисленные выше ограничения a-d на структуру портфеля.

a) Ограничение на суммарный объем активов:

x_A + x_B + x_С + x_D + x_E + x_F £100 000. (2)

b) Ограничение на размер доли каждого актива:

х_А £25 000, х_В £25 000, х_С £ 25 000,

x_d £ 25 000, х_е £ 25 000, x_f £25 000. (3)

c) Ограничение, связанное с необходимостью вкладывать половину средств в долгосрочные активы:

х_В + х_С ³ 50 000 (4)

d) Ограничение на долю ненадежных активов:

x_C + x_D £ 30 000. (5)

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

х_А ³ 0, х_B ³0, х_C ³ 0, x_D ³0, х_Е ³0, x_F ³ 0. (6)