Задача определения оптимальной цены реализации продукции
Министерство общего и профессионального образования Российской Федерации Самарский Государственный Аэрокосмический университет
Пояснительная записка к курсовому проекту по курсу Теория принятия решений Задача определения оптимальной цены реализации продукции. Вариант 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. Метод Баранкина-Дорфмана
Задача формулируется следующим образом (в матричном виде):
Px+xCx -> min,£ b,
x ³ 0
Исходя из теоремы Куна-Таккера, обозначим:
В данном случае условия Куна - Таккера запишутся в виде:
Ax + y = b; (1)
Cx - v + Al = -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||,
такой, что
zI=zi+N, zI+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=d0d0.
Далее tj=?>0 и z = d0+ ?dj. Увеличиваем переменную tj пока некоторая j-ая из базисных переменных не обратится в нуль. Она определяется из условия:
при dgi<0.
Тогда новое базисное решение: z = d0 + ?idj, а величина T соответственно
j = T + ?jkj,
где Kj=2?j+ ?j?j,
где ?j=djd0 и ?j=djdj.
Очевидно, что kj<0. Если таких несколько, то выбирается то, которому соответствует наименьшее отрицательное произведение ?jkj.
б) вычислительная схема
После определения допустимого базисного решения строят симплексную и дополнительную таблицы в виде табл.1.
Таблица 1.
В отличие от стандартной симплекс-таблицы здесь добавлена таблица для дополнительных переменных ? 0, ? j, ?j, ?j, kj, которые вычисляются по следующим формулам:
? 0 = T = d0d0=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.
Матрица С выполняет требования, т.к. является симметричной и положительно полуопределенной, что гарантирует выпуклость целевой функции. Для нашей задачи из выражения (5) (см. выше) получим:
Откуда можно получить следующие уравнения:
-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
1V1V2V3P18500/30.330.50.5P27900/4.20.2380.50.5P313200/1.340.750.50.5Y16500.50.750.75Y211500.51.051.05Y348000.50.3350.335Y42000.50.50.50.750.050.3352.135V11V21V311111? j0? j?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 с.
Больше работ по теме:
Предмет: Информационное обеспечение, программирование
Тип работы: Курсовая работа (т)
Новости образования
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ