Задача определения оптимальной цены реализации продукции
Министерство общего и
профессионального образования Российской Федерации Самарский Государственный
Аэрокосмический университет
Пояснительная записка к курсовому
проекту по курсу “Теория принятия решений” Задача определения оптимальной цены
реализации продукции. Вариант 98
Выполнил: студентка 632 гр. Фиалко А.М.
Самара 2006
Постановка задачи
Вариант 98
Производственное объединение реализует n видов промышленной продукции на мировом рынке в условиях
конкуренции со стороны других фирм. Известно, что объем реализации i-го вида продукции зависит линейно от
цены единицы этого вида продукции pi : Vi = ai*pi+bi : чем меньше цена, тем больший объем
продукции можно реализовать.
Возможности объединения по изготовлению продукции i-го вида ограничены величиной di, а сумма возможностей ограничена d0.
Определить оптимальный набор цен, по которым следует реализовывать все
виды продукции при условии получения наибольшей стоимости реализованной
продукции.
Параметры:1 = -1.52 = -2.13 = -0.671 =
85002 = 7900
b3 = 13200
d1 = 4900
d2 = 5100
d3 = 11300
d0 = 15000
Реферат
Курсовая работа.
Пояснительная записка: 13 стр., 2 таблицы, 4 источника.
Ключевые слова: КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ, НЕЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ, МЕТОД БАРАНКИНА И ДОРФМАНА, МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ,
ЦЕЛЕВАЯ ФУНКЦИЯ, ОГАРНИЧЕНИЯ - НЕРАВЕНСТВА, ОПТИМАЛЬНОЕ РЕШЕНИЕ.
Исследована задача определения оптимальной цены реализации продукции. При
расчете использован метод Баранкина и Дорфмана, а также выполнена программная
реализация решения задачи в пакете GINO. Получено оптимальное решение
поставленной задачи.
стоимость цена программный
1. Математическое моделирование
i - объем реализации i-го вида продукции,i -
цена единицы i-го вида продукции,i - объем производства i-го вида
продукции,0 - общий объем производства продукции,i, bi
- коэффициенты в заданном уравнении,
i = 1,2,3.
Здесь ai, bi,
di, d0 являются постоянными величинами, а pi
- управляемые переменные, которые нужно подобрать таким образом, чтобы
реализовать все виды продукции с получением наибольшей стоимости. Управляемых
переменных 3, а ограничений - 10.
Тогда математическая модель
имеет вид:
F = a1p12 + b1p1 + a2p22 + b2p2 + a3p32 + b3p3-> max
1) -1.5p1+8500£4900;
2) -2.1p2+7900£5100;
) -0.67p3+13200£11300;
) -1.5p1-2.1p2-0.67p3+29600£15000;
) p1³0;
) p2³0;
) p3³0;
) V1³0;
) V2³0;
) V3³0.
Эта задача относится к классу задач квадратичного программирования.
2. Обоснование и выбор метода решения
Данная задача принадлежит к типу задач квадратичного программирования.
Это частный случай задачи нелинейного программирования.
Вообще, основной недостаток методов нелинейного программирования
заключается в том, что с их помощью не удается найти глобальный экстремум при
наличии нескольких локальных экстремумов. Поэтому метод считается теоретически
разработанным, если найдены соотношения, являющиеся необходимыми и достаточными
условиями оптимума, и алгоритмы поиска экстремума с доказательством их
сходимости. Этим требованиям удовлетворяют только методы, рассматриваемые в
разделе квадратичного программирования, частично методы решения задач с
сепарабельными функциями и в значительно меньшей степени прямые методы.
Задача нелинейного программирования.
Рассмотрим задачу математического программирования:
, (1а)
(2а)
(3а)
, , (4а)
здесь
F(x) - целевая функция, выражение (2) - ограничения равенства, выражение (3) -
ограничения неравенства, x - вектор переменных, Dj - некоторые
множества.
Если
хотя бы одна из функций F(x), φi(x) - нелинейная, то это модель задачи нелинейного
программирования. Решение подобных задач возможно только для некоторых классов
функций F(x), φi(x), и
когда Dj - множество действительных чисел
Задача
квадратичного программирования = частный случай задачи нелинейного
программирования, в которой целевая функция = сумма линейной и квадратичной
функции, а все ограничения линейны:
, (5а)
, (6а)
(7а)
или
в матричном виде (P,x,B - векторы-столбцы):
, (8а)
, (9а)
(10а)
В
выражении (8а) матрица С должна быть симметричной и положительно
полуопределенной - это гарантирует выпуклость целевой функции (5а). Известно,
что для задачи выпуклого нелинейного программирования справедлива теорема
Куна-Таккера, выражающая необходимые условия того, что точка x0 является
решением задачи нелинейного программирования:
(11а)
(12а)
где
Ф=Ф(x,λ) - функция Лагранжа.
Теоретически наиболее широко и детально в нелинейном программировании
разработан раздел выпуклого программирования, называемый квадратичным.
Методы квадратичного программирования можно разделить на три группы:
- Алгоритмы, использующие симплекс-метод;
- Градиентные методы;
Прочие специальные методы.
3. Метод Баранкина-Дорфмана
Задача формулируется следующим образом (в матричном виде):
P’x+x’Cx -> min,£ b,
x ³ 0
Исходя из теоремы Куна-Таккера, обозначим:
В данном случае условия Куна - Таккера запишутся в виде:
Ax + y = b; (1)
Cx - v + A’l = -p; (2)
x ³ 0, Y ³ 0, V ³ 0, l ³ 0; (3)+ Yl = 0. (4)
Отметим, что последнее равенство (4) может выполняться только для допустимого
базисного решения системы, которое характеризуется той особенностью, что из
(n + m) ограниченных по знаку переменных x, V, Y, l самое большое N переменных, где N =
n + m - число равенств в этой системе, отличны от нуля.
Идея метода Баранкина и Дорфмана заключается в том, что процедура
последовательного отыскания решения начинается с базисного решения системы
(1)-(3), которое не обязательно удовлетворяет условию (4). Затем с
использованием симплекс-метода добиваются равенства нулю выпуклой функции xv +
yl.
а) алгоритм:
Для удобства изложения все переменные представим в виде 2N - мерного
вектора
= ||x,y,v, l||
.
Можно поставить в соответствии каждому вектору z вектор z’, определяемый
соотношением
’ = ||v, l,x,y||,
такой, что
z’I=zi+N, z’I+N=zi, = 1,2,..,N,
xV+Yl = 1/2zz’.
С помощью этих векторов, условия (1) - (4) запишутся в виде:
(5)(z) = zz’ = 0, z ³ 0.
Исходя из некоторого допустимого базисного решения системы (5), совершим
последовательность симплекс преобразований, с помощью которых будем уменьшать
выпуклую функцию T(z) = zz’, пока не достигнем значения T = 0.
Допустим, имеется некоторое допустимое базисное решение системы (5).
Симплекс - таблица в данном случае должна задавать входящие в базис переменные
zg как функцию от N небазисных переменных zvh=th,
не входящих в базис:
,
g=1,2,..,2N. (6)
эту запись можно использовать и для небазисных переменных из числа zg.
Для этого симплекс-таблица дополняется строками, все элементы которой (кроме
одного, равного единице) равны нулю. В этих строках для небазисной переменной zg
= tj будет dgh = 0, h =j, a dgj = 1.
функциональную зависимость (6) можно записать в векторном виде:
. (7)
При небазисных переменных th = 0 формула (7) перепишется в
виде
= d0 ≥ 0, T=d0d’0.
Далее tj=θ>0 и z = d0+ θdj. Увеличиваем переменную
tj пока некоторая j-ая из базисных переменных не обратится в нуль.
Она определяется из условия:
при
dgi<0.
Тогда
новое базисное решение: z’ = d0 + θidj,
а величина T соответственно
j = T + θjkj,
где
Kj=2αj+ θjβj,
где
αj=djd’0
и βj=djd’j.
Очевидно,
что kj<0. Если таких несколько, то выбирается то, которому
соответствует наименьшее отрицательное произведение θjkj.
б)
вычислительная схема
После
определения допустимого базисного решения строят симплексную и дополнительную
таблицы в виде табл.1.
Таблица
1.
В
отличие от стандартной симплекс-таблицы здесь добавлена таблица для
дополнительных переменных α 0,
α j, βj, θj, kj, которые вычисляются по следующим
формулам:
α 0 = T = d0d’0=2∑di0di+N,0
При
α 0 = 0 сразу получаем оптимальное решение.
В противном случае дополнительно находим:
α j = ∑(dijdi+N,0 + di+N,jdi,0),
j = 1,…,N.
Далее
для j , для которых α j < 0, определяются:
βj = 2∑dijdi+N,j;
при dgj
< 0.
Для
определения элемента j вычисляются:
j = 2 α j + βjθj .
В
качестве заменяющего столбца выбирается такой, для которого отрицательное
произведение θj Kj наименьшее.
Элемент dgj , по которому определено θj ,
становится опорным, и из базиса удаляется соответствующая ему g-я переменная,
которая встает на место переменной заменяющего столбца. Затем все его элементы
делятся на опорный, который при этом становится равным единице. Тем самым
получаем заменяющий столбец с новыми элементами. Для получения остальных
столбцов новой таблицы, из соответствующих столбцов старой вычитаем уже
построенный заменяющий столбец, умноженный на элемент, стоящий на пересечении
преобразуемого столбца старой таблицы и заменяющей строки.
5. Использование метода для решения задачи
В настоящее время подобные задачи легко решаются при помощи современных
ЭВМ. Для решения данной задачи воспользуемся пакетом программ Gino. Но прежде
решим ее вручную.
Решение задачи.
Поиск решения задачи начинается с приведения составленной целевой функции
к минимуму:
L’ = 1.5p12 -8500p1 + 2.1p22
- 7900p2 + 0.67p32 - 13200p3->
min
)-1.5p1+9500 £ 4900;
)-2.1p2+7900 £ 5100;
)-0.67p3+13200 £ 11300;
)-1.5p1-2.1p2-0.67p3+29600 £ 15000;
)p1 ³ 0;
)p2 ³ 0;
)p3 ³ 0;
)V1 ³ 0;
9)V2 ³ 0;
)V3 ³ 0.
Составим следующие матрицы:
n = 3, m = 4, N = 7, 2N = 14.
Откуда можно получить следующие уравнения:
-1.5*p1 + Y1 = -3600;
.1*p2 + Y2 = -2800;
.67*p3 +Y3 = -1900;
.5*p1 -2.1*p2 - 0.67*p3 + Y4 = -14600; (8)
*p1 - V1 -1.5* λ1 -1.5* λ4 = 8500;
.2*p2 - V2 - 2.1*λ2 - 2.1*λ4 = 7900;
.34*p3 - V3 - 0.67*λ3 - 0.67*λ4 = 13200.
Для получения допустимого базисного решения (опорного решения) можно
использовать любой метод отыскания опорного решения задачи ЛП. Для системы (8)
достаточно выбрать p1,p2,p3,Y1,Y2,Y3,Y4 базисными, тогда:
Значит
P1 = 8500/3, P2 = 7900/4.2, P3 = 13200/1.34, Y1 = 650, Y2 = 1150, Y3 = 4800, Y4
= 200- опорное решение. Составим симплекс-таблицу, учтя, что знаки
коэффициентов при свободных переменных (в отличии от симплекс-таблицы задачи
ЛП) не меняются. Пустые клетки соответствуют нулевым коэффициентам.
Таблица
2
|
1
|
V1
|
V2
|
V3
|
|
|
|
|
P1
|
8500/3
|
0.33
|
|
|
0.5
|
|
|
0.5
|
P2
|
7900/4.2
|
|
0.238
|
|
|
|
0.5
|
0.5
|
P3
|
13200/1.34
|
|
|
0.75
|
|
|
0.5
|
0.5
|
Y1
|
650
|
0.5
|
|
|
0.75
|
|
|
0.75
|
Y2
|
1150
|
|
0.5
|
|
|
1.05
|
|
1.05
|
Y3
|
4800
|
|
|
0.5
|
|
|
0.335
|
0.335
|
Y4
|
200
|
0.5
|
0.5
|
0.5
|
0.75
|
0.05
|
0.335
|
2.135
|
V1
|
|
1
|
|
|
|
|
|
|
V2
|
|
|
1
|
|
|
|
|
|
V3
|
|
|
|
1
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
1
|
|
|
|
|
|
|
|
|
α j
|
0
|
|
|
|
|
|
|
|
β j
|
|
|
|
|
|
|
|
|
Κj
|
|
|
|
|
|
|
|
|
Т.к. α0=0,
то сразу получаем оптимальное решение:
P1 = 2833.33;= 1880.95;= 9850.746;=650,
Y2=1150,Y3=4800,Y4=200; =0, V2=0,V3=0;
λ1=0, λ2=0, λ3=0, λ4=0.
6. Использование компьютерных средств для решения задачи
Сравним полученное решение с решением на пакете программ GINO.- система
для решения задач нелинейного, квадратичного программирования, разработанная
для широкого круга пользователей.
С другой стороны, GINO используется для решения промышленных нелинейных,
квадратичных программ значительного размера (более 10000 строк и несколько
тысяч переменных).
Чтобы решить данную задачу нужно составить программную модель. Эта модель
имеет следующий вид:
MODEL:
1) max=-1.5*X1^2-2.1*X2^2-0.67*X3^2+8500*X1+7900*X2+13200*X3;
) -1.5*X1+7900 < 4900;
) -2.1*X2+7900 < 5100 ;
) -0.67*X3+13200 < 11300;
) -1.5*X1-2.1*X2-0.67*X3+29600 < 15000;
) X1>0 ;
) X2 > 0 ;
) X3 > 0;
Программу можно набрать вручную, либо загрузить из файла c помощью
команды take<имя файла>. Командой Look all можно просмотреть весь этот
файл. Чтобы получить решение задачи нужно выполнить команду go.
В результате работы на пакете программ GINO было получено оптимальное
решение. Оно совпало с решением задачи “вручную”.
TOTAL FRACTIONAL CHANGE IN OBJECTIVE LESS THAN 1.00000E-04
FOR 4 CONSECUTIVEFUNCTION VALUE
) 84486352.615718VALUE REDUCED COST2833.181956
.0000001880.886440 .0000009850.676452 .000000SLACK OR SURPLUS PRICE
2) 1249.772933 .000000
) 1149.861344 .000000
) 4699.953387 .000000
) 199.587665 .000000
) 2833.181956 .000000
) 1880.886440 .000000
) 9850.676452 .000000
Список использованной литературы
1. Есипов Б.А. Лекции по курсу “Теория принятия решений”,
2001
2. Решение задач по курсу “Исследование операций”:
нелинейное программирование. / методические указания, составитель Есипов Б.А.,
Куйбышев, 1988, 42с.
. Линейное и нелинейное программирование / под ред.
Е.Е. Караваева. - М.: Наука, 1999, 190 с.
. Кузнецов Ю.Н., Кузубов В.Н., Волощенко А.Б.
Математическое программирование. М.: Высшая школа, 1980, 190 с.