Теория принятия решений

 

Министерство общего и профессионального образования  Российской Федерации 
Самарский Государственный Аэрокосмический университет 

Пояснительная записка  к курсовому проекту по курсу 
“Теория принятия решений” 
Задача определения оптимальной цены реализации продукции. 
Вариант 98

Выполнил: студентка 632 гр. Фиалко А. М. 
Руководитель проекта: Есипов Б.А.

 

Самара 2006

 

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

Вариант 98

 

Производственное объединение  реализует n видов промышленной продукции на мировом рынке в условиях конкуренции со стороны других фирм. Известно, что объем реализации i-го вида продукции зависит линейно от цены единицы этого вида продукции p_i : V_i =  a_i*p_i+b_i : чем меньше цена, тем больший объем продукции можно реализовать.

Возможности объединения по изготовлению продукции i-го вида ограничены величиной d_i, а сумма возможностей ограничена d₀.

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

 

Параметры:

a₁ = -1.5

a₂ = -2.1

a₃ = -0.67

b₁ = 8500

b₂ = 7900

b₃ = 13200

d₁ = 4900

d₂ = 5100

d₃ = 11300

d₀ = 15000

 

РЕФЕРАТ

 

Курсовая работа.

Пояснительная записка:   13 стр., 2 таблицы, 4 источника.

 

Ключевые слова: КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ, НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, МЕТОД БАРАНКИНА И ДОРФМАНА, МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ, ЦЕЛЕВАЯ ФУНКЦИЯ, ОГАРНИЧЕНИЯ – НЕРАВЕНСТВА, ОПТИМАЛЬНОЕ РЕШЕНИЕ.

 

      Исследована задача определения  оптимальной цены реализации  продукции. При расчете использован  метод Баранкина и Дорфмана, а  также выполнена программная реализация решения задачи в пакете GINO. Получено оптимальное решение поставленной задачи.

 

Содержание

 

 

Математическое моделирование

 

V_i – объем реализации i-го вида продукции,

p_i – цена единицы i-го вида продукции,

d_i – объем производства i-го вида продукции,

d₀ – общий объем производства продукции,

a_i, b_i – коэффициенты в заданном уравнении,

i = 1,2,3.

 

Здесь a_i, b_i, d_i, d₀ являются постоянными величинами, а p_i – управляемые переменные, которые нужно подобрать таким образом, чтобы реализовать все виды продукции с получением наибольшей стоимости. Управляемых переменных 3, а ограничений – 10.

Тогда математическая модель имеет  вид:

 

F = a₁p₁² + b₁p₁ + a₂p₂² + b₂p₂ + a₃p₃² + b₃p₃-> max

 

1. –1.5p₁+8500£4900;
2. –2.1p₂+7900£5100;
3. –0.67p₃+13200£11300;
4. –1.5p₁–2.1p₂–0.67p₃+29600£15000;
5. p₁³0;
6. p₂³0;
7. p₃³0;
8. V₁³0;
9. V₂³0;
10. V₃³0.

Эта задача относится  к классу задач квадратичного  программирования.

 

Обоснование и выбор метода решения

 

Данная задача принадлежит  к типу задач квадратичного программирования. Это частный случай задачи нелинейного  программирования.

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

 

Задача нелинейного программирования.

Рассмотрим задачу математического  программирования:

,        (1а)

              (2а)

            (3а)

,      ,        (4а)

здесь F(x) – целевая функция, выражение (2) – ограничения равенства, выражение (3) – ограничения неравенства, x – вектор переменных, D_j – некоторые множества.

Если хотя бы одна из функций F(x), φ_i(x) - нелинейная, то это модель задачи нелинейного программирования. Решение подобных задач возможно только для некоторых классов функций F(x), φ_i(x), и когда D_j - множество действительных чисел

Задача квадратичного  программирования = частный случай задачи нелинейного программирования, в которой целевая функция = сумма линейной и квадратичной функции, а все ограничения линейны:

,  (5а)

,      (6а)

         (7а)

 

или в матричном виде  (P,x,B – векторы-столбцы):

,      (8а)

,          (9а)

           (10а)

В выражении (8а) матрица С должна быть симметричной и положительно полуопределенной – это гарантирует выпуклость целевой функции (5а). Известно, что для задачи выпуклого нелинейного программирования справедлива теорема Куна-Таккера, выражающая необходимые условия того, что точка x₀ является решением задачи  нелинейного программирования:

(11а)

    

(12а)

    

 

где Ф=Ф(x,λ) – функция  Лагранжа.

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

Методы квадратичного  программирования можно разделить  на три группы:

• Алгоритмы, использующие симплекс-метод;
• Градиентные методы;
• Прочие специальные методы.

 

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

Метод Баранкина - Дорфмана

 

Задача формулируется  следующим образом (в матричном  виде):

P’x+x’Cx -> min,

Ax £ b,

x ³ 0

Исходя из теоремы Куна-Таккера, обозначим:

 

 

В данном случае условия Куна –  Таккера запишутся в виде:

  Ax + y = b;                                     (1)                     

2Cx - v + A’l = -p;                         (2) 

x ³ 0, Y ³ 0, V ³ 0, l ³ 0;               (3)

xV + Yl = 0.                                    (4)

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

2(n + m) ограниченных по  знаку переменных x, V, Y,  l самое большое N переменных, где N = n + m – число равенств в этой системе, отличны от нуля.

Идея метода Баранкина и Дорфмана заключается в том, что процедура последовательного отыскания решения начинается с базисного решения системы (1)-(3), которое не обязательно удовлетворяет условию (4). Затем с использованием симплекс-метода добиваются равенства нулю выпуклой функции xv + yl.

 

а) алгоритм:

Для удобства изложения все переменные представим в виде 2N – мерного  вектора

Z = ||x,y,v, l|| .

Можно поставить в  соответствии каждому вектору z вектор z’, определяемый соотношением

Z’ = ||v, l,x,y||,

такой, что

z’_I=z_i+N, z’_I+N=z_i,

i = 1,2,..,N,

 

xV+Yl = 1/2zz’.

С помощью этих векторов, условия (1) – (4) запишутся в виде:

 

 

		A	E	0	0		z     =		B		(5)
		2C	0	-E	AT				-p

 

     T(z) = zz’ = 0, z ³ 0.

Исходя из некоторого допустимого базисного решения системы (5), совершим последовательность симплекс преобразований, с помощью которых будем уменьшать выпуклую функцию T(z) = zz’, пока не достигнем значения T = 0.

Допустим, имеется некоторое  допустимое базисное решение системы (5). Симплекс – таблица в данном случае должна задавать входящие в базис переменные z_g как функцию от N небазисных переменных z_vh=t_h, не входящих в базис:

 

, g=1,2,..,2N.                          (6)

эту запись можно использовать и для небазисных переменных из числа z_g. Для этого симплекс-таблица дополняется строками, все элементы которой (кроме одного, равного единице) равны нулю. В этих строках для небазисной переменной z_{g =} t_j будет d_gh = 0, h =j, a d_gj = 1. функциональную зависимость (6) можно записать в векторном виде:

    .                                               (7)

 При небазисных  переменных t_h = 0 формула (7) перепишется в виде

Z = d₀ ≥ 0,   T=d₀d’₀.

Далее t_j=θ>0 и z = d₀+ θd_j. Увеличиваем переменную t_j пока некоторая j-ая из базисных переменных не обратится в нуль. Она определяется из условия:

 при d_gi<0.

Тогда новое базисное решение: z’ = d₀ + θ_id_j, а величина T  соответственно

T_j = T + θ_jk_j,    где   

K_j=2α_j+ θ_jβ_j,     где

α_j=d_jd’₀  и  β_j=d_jd’_j.

 

Очевидно, что k_j<0. Если таких несколько, то выбирается то, которому соответствует наименьшее отрицательное произведение θ_jk_j.

 

б) вычислительная схема

После определения допустимого  базисного решения строят симплексную  и дополнительную таблицы в виде табл.1.

                                        1                                    z1                   …     zN  

 

   Симпл   x1=z1                 d10                            d11                     …   d1,N

   Табл   … 

              …

               ym=zN             dN,0                          dN,1                   …   dN,N

               V1=zN+1          dN+1,0                      dN+1,1             …   dN+1,N   

              …

              … 

               λm=z2N            d2N,0                        d2N,1                …   d2N,N  

                                                                               α1                  …   αN   

  дополнительная            α0                                 β1                  …   βN

  таблица                                                                θ1                  …   θN   

                                                                               k1                  …   kN

 

таблица 1.

 

 

В  отличие от стандартной симплекс-таблицы здесь добавлена таблица для дополнительных переменных  α _0, α _j, βj, θj, k_j, которые вычисляются по следующим формулам:

 

α ₀ = T = d₀d’₀=2∑d_i0d_i+N,0

 

При α ₀ = 0 сразу получаем оптимальное решение. В противном случае дополнительно находим:

 

α _j = ∑(d_ijd_i+N,0 + d_i+N,jd_i,0),   j = 1,…,N.

 

Далее для j , для которых  α _j < 0, определяются:

 

β_j = 2∑d_ijd_i+N,j ;

 

 при d_gj < 0.

Для определения элемента j вычисляются:

 

K_j = 2 α _j + β_jθ_j .

 

В качестве заменяющего столбца выбирается такой, для которого отрицательное произведение θ_j K_j наименьшее. Элемент d_gj , по которому определено θ_j , становится опорным, и из базиса удаляется соответствующая ему g-я переменная, которая встает на место переменной заменяющего столбца. Затем все его элементы делятся на опорный, который при этом становится равным единице. Тем самым получаем заменяющий столбец с новыми элементами. Для получения остальных столбцов новой таблицы, из соответствующих столбцов старой вычитаем уже построенный заменяющий столбец, умноженный на элемент, стоящий на пересечении преобразуемого столбца старой таблицы и заменяющей строки.

 

Использование метода для  решения задачи.

 

В настоящее время  подобные задачи легко решаются при  помощи современных ЭВМ. Для решения данной задачи воспользуемся пакетом программ Gino. Но прежде решим ее вручную.

Решение задачи.

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

 

L’ = 1.5p₁² -8500p₁ + 2.1p₂² - 7900p₂ + 0.67p₃² - 13200p₃-> min