Задача определения оптимальной цены реализации продукции

Тип работы:
Курсовая
Предмет:
Программирование


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

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

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

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

Самара 2006

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

Вариант 98

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

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

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

Параметры:

a1 = -1. 5

a2 = -2. 1

a3 = -0. 67

b1 = 8500

b2 = 7900

b3 = 13 200

d1 = 4900

d2 = 5100

d3 = 11 300

d0 = 15 000

Реферат

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

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

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

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

стоимость цена программный

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

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

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

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

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

ai, bi — коэффициенты в заданном уравнении,

i = 1,2,3.

Здесь ai, bi, di, d0 являются постоянными величинами, а pi — управляемые переменные, которые нужно подобрать таким образом, чтобы реализовать все виды продукции с получением наибольшей стоимости. Управляемых переменных 3, а ограничений — 10.

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

F = a1p12 + b1p1 + a2p22 + b2p2 + a3p32 + b3p3-> max

1) -1. 5p1+85 004 900;

2) -2. 1p2+79 005 100;

3) -0. 67p3+1 320 011 300;

4) -1. 5p1-2. 1p2-0. 67p3+2 960 015 000;

5) p10;

6) p20;

7) p30;

8) V10;

9) V20;

10) V30.

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

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,

Ax b,

x 0

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

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

Ax + y = b; (1)

2Cx — v + A' = -p; (2)

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

xV + Y = 0. (4)

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

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

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

а) алгоритм:

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

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

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

Z' = ||v,, x, y||,

такой, что

z'I=zi+N, z'I+N=zi,

i = 1,2,., N,

xV+Y = ½zz'.

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

(5)

T (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) перепишется в виде

Z = d0? 0, T=d0d'0.

Далее tj=?>0 и z = d0+ ?dj. Увеличиваем переменную tj пока некоторая j-ая из базисных переменных не обратится в нуль. Она определяется из условия:

при dgi<0.

Тогда новое базисное решение: z' = d0 + ?idj, а величина T соответственно

Tj = 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 вычисляются:

Kj = 2? j + ?j?j.

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

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

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

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

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

L' = 1. 5p12 -8500p1 + 2. 1p22 — 7900p2 + 0. 67p32 — 13200p3-> min

1)-1. 5p1+9500 4900;

2)-2. 1p2+7900 5100;

3)-0. 67p3+13 200 11 300;

4)-1. 5p1-2. 1p2-0. 67p3+29 600 15 000;

5)p1 0;

6)p2 0;

7)p3 0;

8)V1 0;

9)V2 0;

10)V3 0.

Составим следующие матрицы:

n = 3, m = 4, N = 7, 2N = 14.

Матрица С выполняет требования, т.к. является симметричной и положительно полуопределенной, что гарантирует выпуклость целевой функции. Для нашей задачи из выражения (5) (см. выше) получим:

Откуда можно получить следующие уравнения:

-1. 5*p1 + Y1 = -3600;

-2. 1*p2 + Y2 = -2800;

-0. 67*p3 +Y3 = -1900;

-1. 5*p1 -2. 1*p2 — 0. 67*p3 + Y4 = -14 600; (8)

3*p1 — V1 -1. 5* ?1 -1. 5* ?4 = 8500;

4. 2*p2 — V2 — 2. 1*?2 — 2. 1*?4 = 7900;

1. 34*p3 — V3 — 0. 67*?3 — 0. 67*?4 = 13 200.

Для получения допустимого базисного решения (опорного решения) можно использовать любой метод отыскания опорного решения задачи ЛП. Для системы (8) достаточно выбрать p1, p2,p3,Y1,Y2,Y3,Y4 базисными, тогда:

Значит P1 = 8500/3, P2 = 7900/4. 2, P3 = 13 200/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

13 200/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

?j

Т.к. ?0=0, то сразу получаем оптимальное решение:

P1 = 2833. 33;

P2 = 1880. 95;

P3 = 9850. 746;

Y1=650, Y2=1150,Y3=4800,Y4=200;

V1=0, V2=0,V3=0;

?1=0, ?2=0, ?3=0, ?4=0.

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

Сравним полученное решение с решением на пакете программ GINO.

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

С другой стороны, GINO используется для решения промышленных нелинейных, квадратичных программ значительного размера (более 10 000 строк и несколько тысяч переменных).

Чтобы решить данную задачу нужно составить программную модель. Эта модель имеет следующий вид:

MODEL:

1) max=-1. 5*X12−2. 1*X22−0. 67*X32+8500*X1+7900*X2+13 200*X3;

2) -1. 5*X1+7900 < 4900;

3) -2. 1*X2+7900 < 5100;

4) -0. 67*X3+13 200 < 11 300;

5) -1. 5*X1−2. 1*X2−0. 67*X3+29 600 < 15 000;

6) X1>0;

7) X2 > 0;

8) X3 > 0;

END

Программу можно набрать вручную, либо загрузить из файла c помощью команды take< имя файла>. Командой Look all можно просмотреть весь этот файл. Чтобы получить решение задачи нужно выполнить команду go.

В результате работы на пакете программ GINO было получено оптимальное решение. Оно совпало с решением задачи «вручную».

TOTAL FRACTIONAL CHANGE IN OBJECTIVE LESS THAN 1. 00000E-04 FOR 4 CONSECUTIVE

ITERATIONS

OBJECTIVE FUNCTION VALUE

1) 84 486 352. 615 718

VARIABLE VALUE REDUCED COST

X1 2833. 181 956. 0

X2 1880. 886 440. 0

X3 9850. 676 452. 0

ROW SLACK OR SURPLUS PRICE

2) 1249. 772 933. 0

3) 1149. 861 344. 0

4) 4699. 953 387. 0

5) 199. 587 665. 0

6) 2833. 181 956. 0

7) 1880. 886 440. 0

8) 9850. 676 452. 0

Список использованной литературы

1. Есипов Б. А. Лекции по курсу «Теория принятия решений», 2001

2. Решение задач по курсу «Исследование операций»: нелинейное программирование. / методические указания, составитель Есипов Б. А., Куйбышев, 1988, 42с.

3. Линейное и нелинейное программирование / под ред. Е. Е. Караваева. — М.: Наука, 1999, 190 с.

4. Кузнецов Ю. Н., Кузубов В. Н., Волощенко А. Б. Математическое программирование. М.: Высшая школа, 1980, 190 с.

Показать Свернуть
Заполнить форму текущей работой