|
59 Вторая задача заключается в определении оптимальной величины заказа V, так чтобы максимизировать прибыль Центра P = q(v)-V-5„,(F) (2.2.5) Рассмотрим методы решения первой задачи распределения заказа величины V между m производителями так, чтобы минимизировать стоимость заказа. Формальная постановка задачи следующая. Требуется так определить величины Х (с> О, чтобы общий объем заказа был не менее V, то есть 1 Л I x i S V , к ! ш а стоимость заказа s = ^Sk(Xk), где Sk(xk) = ХкЬк(Хк), к>1 была минимальной. Сложность решения этой задачи определяется тем, что функции Ьк(хк) разрывные (имеют скачки). Так на рис. 2.2.5 приведен вид функции хЬ(х) для производителя продукции из примера 2.2.1. Задачи такого вида называются многоэкстремальными задачами математического профаммирования. Для решения таких задач, как правило, применяются специальные методы (динамического профаммирования, локальной оптимизации, ветвей и фаниц и другие). Мы рассмотрим применение для решения задачи метода ветвей и фаЕсиц. Описание метода проведем на конкретном примере. Пусть есть два производителя. Функция S(x) первого производителя имеет вид, показанный на рис. 2.2.5, а второго на рис. 2.2.6. Пусть V = 15, первый производитель имеет 12 единиц продукции, а второй 10. |
васм варианты последовательно, начиная с первого. Первый вариант хуже второго, поскольку V < V2, a 8i = 62. Второй вариант лучше третьего, так как Бг/Уз = 3/8 > S3/V2 = V 3. Второй вариант хуже четвертого, так как г2/УА= ’/4< e/V 2= V 3. Наконец, четвертый вариант лучше пятого, так как S 4 / V 5 = 2/ ) 5 > e/V 4= V12. Итак, оптимальным является вариант 4, в котором по централизованной схеме обеспечиваются первые четыре потребителя. При этом объем продукции, заказываемой центром, составляет 12 единиц, оптовая цена производителя равна 1, а цена продукции центра равна 3. Прибыль центра составляет (3-1) • 12 = 24 единицы. 5.2. Разработка стратегии оптимального распределения заказа В предыдущем параграфе предполагалось, что имеется один производитель продукции, которую заказывает центр. В случае нескольких производителей возникает задача распределения заказов между ними [24,31],. Обозначим bk(xk ) цену продукции k-го производителя при его объеме заказа Х кРассмотрим задачу распределения заказа величины V между m производителями так, чтобы минимизировать стоимость заказа. Формальная постановка задачи следующая. Требуется так определить величины хк> 0, чтобы общий объm m ем заказа был не менее V, то есть £xkа V , а стоимость заказа s =]rsk(xk), где к»! lc=I Sk(xk) = Xkbk(xk), была минимальной. Сложность решения этой задачи определяется тем, что функции bk(xk ) разрывные (имеют скачки). Так на рис. 5.2.1 приведен вид функции xb(x) для производителя продукции (см. табл. 5.1.2). 192 Рис. 5.2.1. Задачи такого вида называются многоэкстремальными задачами математического программирования. Для решения таких задач, как правило, применяются специальные методы (динамического программирования, локальной оптимиза ции, ветвей и границ и другие). Рассмотрим применение для решения задачи метода ветвей и границ. Описание метода проведем на конкретном примере. Пусть есть два производителя. Функция S(x) первого производителя имеет вид, показанный на рис. 5.2.1, а второго на рис. 5.2.2. Пусть V = 15, первый производитель имеет 12 единиц продукции, а второй 10. 193 ■S2(x 2) . . . . 5 ,0 Рис. 5.2.2. Сначала опишем метод получения нижней оценки стоимости заказа. Для получения такой оценки заменим функции s^(xk) непрерывными выпуклыми функциями, которые всюду меньше (или равны) исходных функций. Оценочные функции s j(x ,)= X i, s^(xj) = 2 x 2 показаны на рис. 5.2.1 и 5.2.2 толстыми линиями. Решим задачу минимизации суммы оценочных функций. Это задача линейного (в общем случае выпуклого) программирования, для которой существуют эффективные методы решения. В нашем случае решение очевидно. Нужно заказать все имеющееся количество продукции xj = 12 у первого производителя по цене bi = 1, а остальные х2= Зединицы у второго, по цене Ь2= 2. Стоимость заказа составит 18 единиц. Заметим, что фактическая стоимость такого заказа составляет 12 + 3-5 = 27 единиц, поскольку при заказе у второго производителя трех единиц продукции цена составит 3 единицы. Рассмотрим теперь два варианта. В первом варианте заказ у второго производителя не превышает трех единиц, а во втором не меньше трех единиц, то есть разобьем множество всех решений на два подмножества. Рассмотрим первое подмножество. Поскольку заказ у второго производителя не превышает трех единиц, то его оценочная функция будет уже другой, а именно, % (х2)= 5х2. Оптимальное решение оценочной задачи остается прежним: Xi = 12, х2 = 3. Однако, оценка стоимости заказа будет равна уже не 18, а 27, что совпадает с фактической стоимостью. Рассмотрим второе подмножество. Так как заказ у второго производителя в этом подмножестве решений не менее трех единиц, то оценочная функция при х2 |