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

Размещено на

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

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

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

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₁+85004900;

2) -2.1p₂+79005100;

3) -0.67p₃+1320011300;

4) -1.5p₁-2.1p₂-0.67p₃+2960015000;

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 = 1/2zz'.

С помощью этих векторов, условия (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)