Введение.
Задачи параметрического программирования являются обобщением задач линейной оптимизации. Это обобщение состоит в том, что данные в задаче линейной оптимизации считают непостоянными величинами, а функциями, определенным образом зависящие от некоторых параметров.
Если предположить, например, что произведенная предприятием продукция подлежит хранению, то ее стоимость будет складываться из двух частей:
а) постоянной – стоимость продукции на момент изготовления;
б) переменной, зависящей от срока хранения продукции.
Целевую функцию задачи оптимального планирования такого производства можно выразить через коэффициенты, линейно зависящие от одного параметра, в частности от времени t.
Часто на практике встречаются задачи, в которых значение целевой функции известно лишь приближенно. Представив их в виде линейной функции параметра t, можно изучить поведение решений задач при различных значениях этих коэффициентов. Аналогично можно провести исследования для случая, когда изменяются коэффициенты системы ограничений.
Параметрическое программирование и занимается этими исследованиями. Данная теория имеет два метода расчета зависимостей от параметра - графический и аналитический. Эти методы подробно разобраны в данной работе (в аналитической части). Также здесь приведены примеры по каждому из методов (в практической части). Кроме того в данной работе представлена отдельно разработанная задача с экономическим содержанием. В ней продемонстрировано, как время (в данном случае сезонность) влияет на доход предприятия, и как с помощью методов параметрического программирования можно просчитать действия предприятия.
2. Практическая часть. Примеры решения задач с параметром.
2.1 Пример графического решения
Предприятие должно выпустить два вида продукции А и В, для изготовления которых используется три вида сырья. Нормы расхода каждого вида на производство единицы продукции данного вида приведены в табл. 1. В ней же указаны запасы сырья каждого вида, которое может быть использовано на производство единицы продукции данного вида.
Таблица 1
Вид сырья Нормы расхода сырья на производство единицы продукции Запасы сырья
А В
I 4 1 16
II 2 2 22
III 6 3 36
Известно, что цена единицы продукции может изменяться для изделия А от 2 до 12 руб., а для изделия В – от 13 до 3 руб., причем эти изменения определяются соотношением , , где .
Для каждого из возможных значений цены единицы продукции каждого из видов найти такой план их производства, при котором общая стоимость продукции является максимальной.
Решение. Предположим, что предприятие изготовит единиц продукции А и единиц продукции В. Тогда математическая постановка задачи состоит в определении для каждого значения параметра максимального значения функции
(13)
при условиях
(14)
(15)
Чтобы найти решение задачи (13)-(15), строим многоугольник решений, определяемый системой линейных неравенств (14) и условиями неотрицательности переменных (15) (рис. 1). После этого, полагая , строим прямую (число 26 взято произвольно) и вектор С = (2, 13). Передвигая построенную прямую в направлении вектора С, видим, что последней общей точкой ее с многоугольником решений OABCD является точка А (0, 11). Следовательно, задача, полученная из задачи (13)-(15), при , имеет оптимальный план . Это означает, что если цена продукции А равна 2+0 = 2 руб., а цена единицы продукции В равна 13-0 = 13 руб., то оптимальным планом производства является план, согласно которому производится 11 изделий В и не производится изделия А. при таком плане производства продукции ее стоимость максимальна и равна .
Положим теперь и построим прямую и вектор . Передвигая построенную прямую в направлении вектора , видим, что последней ее общей точкой с многоугольником решений является точка А (0, 11). Следовательно при , задача имеет оптимальный план . Это означает, что если цена единицы продукции А = 4 руб., а В = 11 руб., то предприятию выгоднее производить 11 единиц изделия В. При этом максимальная общая стоимость продукции будет равна 121 руб.
Список использованной литературы
1. Абрамов Л.М., Капустин В.Ф. Математическое программирование: Учеб. пособие. Л.: Изд-во Ленингр. Ун-та, 1981.
2. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие. – 2-е изд., испр. и доп. – М.:Высшая школа, 1993.
3. Костевич Л.С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С.Костевич. – Мн.: Новое знание, 2003.
4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учеб. пособие – 2-е изд., перераб. и доп. – М.: Высшая школа, 1980.