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

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

Пояснительная записка к курсовому проекту по курсу «Теория принятия решений» Задача определения оптимальной цены реализации продукции. Вариант 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₃ = 13 200

d₁ = 4900

d₂ = 5100

d₃ = 11 300

d₀ = 15 000

Реферат Курсовая работа.

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

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

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

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

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

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₁+85 004 900;

2) -2.1p₂+79 005 100;

3) -0.67p₃+1 320 011 300;

4) -1.5p₁-2.1p₂-0.67p₃+2 960 015 000;

5) p₁0;

6) p₂0;

7) p₃0;

8) V₁0;

9) V₂0;

10) V₃0.

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

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

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

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

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

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

(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,?) — функция Лагранжа.

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

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

— Алгоритмы, использующие симплекс-метод;

— Градиентные методы;

— Прочие специальные методы.

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

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=z_i+N, z'_I+N=z_i,

i = 1,2,., N,

xV+Y = ½zz'.

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

(5)

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.

В отличие от стандартной симплекс-таблицы здесь добавлена таблица для дополнительных переменных? _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, j}d_{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-я переменная, которая встает на место переменной заменяющего столбца. Затем все его элементы делятся на опорный, который при этом становится равным единице. Тем самым получаем заменяющий столбец с новыми элементами. Для получения остальных столбцов новой таблицы, из соответствующих столбцов старой вычитаем уже построенный заменяющий столбец, умноженный на элемент, стоящий на пересечении преобразуемого столбца старой таблицы и заменяющей строки.

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

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

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

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

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

1)-1.5p₁+9500 4900;

2)-2.1p₂+7900 5100;

3)-0.67p₃+13 200 11 300;

4)-1.5p₁-2.1p₂-0.67p₃+29 600 15 000;

5)p₁ 0;

6)p₂ 0;

7)p₃ 0;

8)V₁ 0;

9)V₂ 0;

10)V₃ 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

Т.к. ?₀=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*X1²−2.1*X2²−0.67*X3²+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.615718

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 с.