Оптимизация портфеля ценных бумаг с помощью модели Марковица

  План, Х^*=(х₁^*, x₂^* , ..., х_n^*) при котором целевая функция задачи (1.10) принимает свое максимальное (минимальное) значение, называется оптимальным.

  Значение  целевой функции (1.10) при плане X будем обозначать через  
F(X). Следовательно, X* — оптимальный план задачи, если для любого X выполняется неравенство F (X) ≤ F (X*) [соответственно F(X) ≥ F(X*)].

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

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

  В том случае, когда требуется найти  минимум функции F=c₁x₁+ c₂x₂…+ c_nx_n можно перейти к нахождению максимума функции F₁ =-F=-c₁x₁-c₂x₂ …- c_nx_n, поскольку min F = max (—F).

   Ограничение – неравенство исходной задачи линейного программирования, имеющее вид «≤», можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение – неравенство вида «≥» — в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство 

преобразуется в ограничение-равенство

а ограничение-неравенство 

— в ограничение-равенство 

В то же время  каждое уравнение системы ограничений 

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

     Число вводимых дополнительных неотрицательных  переменные при преобразовании ограничений-неравенств в ограничения-равенства равно числу преобразуемых неравенств.

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

     Отметим, наконец, что если переменная x_k не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными u_k и v_k, приняв x_k= u_k - v_k .

1.4.Целочисленные задачи линейного программирования

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

       Определение оптимального плана задачи целочисленного программирования.

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

                                     (1.14)

      при условиях:

                     
 
 

     Если  найти решение задачи (1.14) — (1.17) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (1.14) — (1.17) требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит симплексный метод.

     Метод Гомори.

      Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (1.14) — (1.17) без учета целочисленности переменных. После того, как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (1.14) — (1.17). Если же в оптимальном плане задачи (1.14) — (1.17) переменная      принимает дробное значение, то к системе уравнений (1.15) добавляют неравенство

                                                               (1.18)

      и находят решение задачи (1.14) — (1.17), (1.18)

      В неравенстве (1.18)     и       - преобразованные исходные величины a_ij и b_i, значения которых взяты из симплекс-таблицы, а          и        - дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число bтакое, что разность между а и b есть целое). Если в оптимальном плане задачи (1.14) — (1.16) дробные значения принимают несколько переменных, то дополнительное неравенство (1.18) определяется наибольшей дробной частью.

     Если  в найденном плане задачи (1.14) — (1.16), (1.18) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (1.14) — (1.17), либо устанавливают ее неразрешимость.

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

                                                             (1.19)

     где          определяются из следующих соотношений:

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

                                                                при ≥ 0

                                                                           при < 0 

     

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

                                                                   при ≤

                                                                  при >  

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

     1. Используя симплексный метод,  находят решение задачи (1.14) — (1.16) без учета требования целочисленности переменных.

     2. Составляют дополнительное ограничение  для переменной, которая в оптимальном плане задачи (1.14) — (1.16) имеет максимальное дробное значение, а в оптимальном плане задачи (1.14) — (1.17) должна быть целочисленной.

     3. Используя двойственный симплекс-метод,  находят решение задачи, получающейся из задачи (1.14) — (1.16) в результате присоединения дополнительного ограничения.

     4. В случае необходимости составляют  еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (1.14) — (1.17) или установления ее неразрешимости. 

    Задача 1. Нефтеперерабатывающий завод располагает двумя сортами нефти: сортом А в количестве 10 единиц, сортом В — 15 единиц. При переработке из нефти получаются два материала: бензин (обозначим Б) и мазут (М). Имеется три варианта технологического процесса переработки:

I: 1ед.А  + 2ед.В дает 3ед.Б + 2ед.М  
II:2ед.А + 1ед.В дает 1ед.Б + 5ед.М  
III:2ед.А + 2ед.В дает 1ед.Б + 2ед.М

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

    Обозначим неизвестные величины:

    х_i—количество использования i-го технологического процесса (i=1,2,3).  
Остальные параметры модели (запасы сортов нефти, цены бензина и мазута) известны.  
Теперь одно конкретное решение завода сводится к выбору одного вектора х=( х₁ ,х₂ ,х₃), для которого выручка завода равна (32х₁+15х₂ +12х₃) долл. Здесь 32 долл. — это доход, полученный от одного применения первого технологического процесса (10 долл.·3ед.Б + 1 долл.·2ед.М = 32 долл.). Аналогичный смысл имеют коэффициенты 15 и 12 для второго и третьего технологических процессов соответственно. Учет запаса нефти приводит к следующим условиям:

     для сорта  А:  
        для сорта В:

где в первом неравенстве коэффициенты 1, 2, 2 —  это нормы расхода нефти сорта  А для одноразового применения технологических  процессов I, II, III соответственно. Коэффициенты второго неравенства имеют аналогичный  смысл для нефти сорта В.  
Математическая модель в целом имеет вид:

Найти такой  вектор х = ( х₁ ,х₂ ,х₃),чтобы максимизировать  
f(x) =32х₁+15х₂ +12х₃ при выполнении условий:

 

 

Сокращенная форма  этой записи такова:

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

 
 

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

Решение.

Сформулированную  задачу перепишем так: найти максимальное значение функции

                                                 f(x) =32х₁+15х₂ +12х₃                                    (1.24)

при условиях:                                                                         

(1.25)

 

     Задача  (1.24) — (1.26) является частично целочисленной, так как переменные x₁ , x₂ и x₃ могут принимать нецелочисленные значения.

     Находим симплексным методом решение задачи (1.24) – (1.25)  
(табл. 1).

Таблица 1.