РУБРИКИ |
Динамическое и линейное программирование |
РЕКЛАМА |
|
Динамическое и линейное программированиеДинамическое и линейное программированиеГосударственный университет управления Институт заочного обучения Специальность – менеджмент Кафедра прикладной математики КУРСОВОЙ ПРОЕКТ по дисциплине: «Прикладная математика» Выполнил студент 1-го курса Группа № УП4-1-98/2 Студенческий билет № Москва, 1999 г. Содержание 1. Линейная производственная задача 3 2. Двойственная задача 7 3. Задача о «Расшивке узких мест производства» 9 4. Транспортная задача 12 5. Распределение капитальных вложений 17 6. Динамическая задача управления запасами 21 7. Анализ доходности и риска финансовых операций 26 8. Оптимальный портфель ценных бумаг 28 1. Линейная производственная задача Линейная производственная задача – это задача о рациональном использовании имеющихся ресурсов, для решения которой применяют методы линейного программирования. В общем виде задача может быть сформулирована следующим образом: Предположим, предприятие или цех может выпускать [pic] видов продукции, используя [pic] видов ресурсов. При этом известно количество каждого вида ресурса, расход каждого вида ресурса на выпуск каждого вида продукции, прибыль, получаемая с единицы выпущенной продукции. Требуется составить такой план производства продукции, при котором прибыль, получаемая предприятием, была бы наибольшей. Примем следующие обозначения: |[pic]|Номер ресурса (i=1,2,…,m) | |[pic]|Номер продукции (j=1,2,…,n) | |[pic]|Расход i-го ресурса на единицу j-ой продукции | |[pic]|Имеющееся количество i-го ресурса | |[pic]|Прибыль на единицу j-ой продукции | |[pic]|Планируемое количество единиц j-ой продукции | |[pic] |Искомый план производства | Таким образом, математическая модель задачи состоит в том, чтобы найти производственную программу [pic] максимизирующую прибыль: [pic] При этом, какова бы ни была производственная программа [pic], ее компоненты должны удовлетворять условию, что суммарное использование данного вида ресурса, при производстве всех видов продукции не должно превышать имеющееся количество данного вида ресурса, т.е. [pic], где [pic] А так как компоненты программы – количество изделий, то они не могут быть выражены отрицательными числами, следовательно добавляется еще одно условие: [pic], где [pic] Предположим, что предприятие может выпускать четыре вида продукции ([pic]), используя для этого три вида ресурсов ([pic]). Известна технологическая матрица [pic] затрат любого ресурса на единицу каждой продукции, вектор [pic] объемов ресурсов и вектор [pic] удельной прибыли: [pic] [pic] [pic] Тогда математическая модель задачи будет иметь вид: Найти производственную программу [pic] максимизирующую прибыль: |[pic] |(1.1) | при ограничениях по ресурсам: |[pic] |(1.2) | где по смыслу задачи: [pic], [pic], [pic], [pic] Таким образом, получили задачу на нахождение условного экстремума. Для ее решения введем дополнительные неотрицательные неизвестные: |[pic], |остаток ресурса определенного вида | |[pic], |(неиспользуемое количество каждого | |[pic] |ресурса) | Тогда вместо системы неравенств (1.2), получим систему линейных алгебраических уравнений: |[pic] |(1.3) | где среди всех решений, удовлетворяющих условию неотрицательности: [pic], [pic], [pic], [pic], [pic], [pic], [pic] надо найти решение, при котором функция (1.1) примет наибольшее значение. Эту задачу будем решать методом последовательного улучшения плана – симплексным методом. Воспользуемся тем, что правые части всех уравнений системы (1.3) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные x1, x2, x3, x4, получаем базисное неотрицательное решение: [pic], [pic], [pic], [pic], [pic], [pic], [pic] первые четыре компоненты которого представляют производственную программу [pic], по которой пока ничего не производится. Из выражения (1.1) видно, что наиболее выгодно начинать производить продукцию третьего вида, т.к. прибыль на единицу выпущенной продукции здесь наибольшая, поэтому в системе (1.3) принимаем переменную x3 за разрешающую и преобразуем эту систему к другому предпочитаемому виду. Для чего составляем отношения правых частей уравнений к соответствующим положительным коэффициентам при выбранной неизвестной и находим наибольшее значение x3, которое она может принять при нулевых значениях других свободных неизвестных, сохранив правые части уравнений неотрицательными, т.е. [pic] Оно соответствует первому уравнению в системе (1.3), и показывает какое количество изделий третьего вида предприятие может изготовить с учетом объемов сырья первого вида. Следовательно, в базис вводим неизвестную x3, а исключаем от туда неизвестную x5. Тогда принимаем первое уравнение в системе (1.3) за разрешающее, а разрешающим элементом будет a13=6. Применив формулы исключения, переходим к новому предпочитаемому виду системы с соответствующим базисным допустимым решением. Полный процесс решения приведен в таблице 1, где в последней строке третьей таблицы нет ни одного отрицательного относительного оценочного коэффициента [pic], где [pic], где [pic], т.е. выполняется критерий оптимальности для максимизируемой функции (1.1). |Таблица 1 | |C |Бази|H |30 |11 |45 |6 |0 |0 |0 |Пояснения | | |с | | | | | | | | | | | | | |[pic| |[pic|[pic|[pic|[pic|[pic| | | | | |] | |] |] |] |] |] | | |0 |[pic|15|3 |2 |6 |0 |1 |0 |0 |[pic] | | |] |0 | | | | | | | |x3 – разрешающая| | | | | | | | | | | |переменная | | | | | | | | | | | |x3 ( в базис. | | | | | | | | | | | |[pic] | | | | | | | | | | | |первая строка – | | | | | | | | | | | |разрешающая | | | | | | | | | | | |x5 ( из базиса. | | | | | | | | | | | |разрешающий | | | | | | | | | | | |элемент = 6 | |0 |[pic|13|4 |2 |3 |5 |0 |1 |0 | | | |] |0 | | | | | | | | | |0 |[pic|12|4 |3 |2 |4 |0 |0 |1 | | | |] |4 | | | | | | | | | | |0 | |-30 |-11 |-45 |-6 |0 |0 |0 | | |45|[pic|25|[pic|[pic|1 |0 |[pic|0 |0 |[pic] | | |] | |] |] | | |] | | |x1 – разрешающая| | | | | | | | | | | |переменная | | | | | | | | | | | |[pic] | | | | | | | | | | | |вторая строка – | | | | | | | | | | | |разрешающая | | | | | | | | | | | |разрешающий | | | | | | | | | | | |элемент = [pic] | |0 |[pic|55|[pic|1 |0 |5 |[pic|1 |0 | | | |] | |] | | | |] | | | | |0 |[pic|74|3 |[pic|0 |4 |[pic|0 |1 | | | |] | | |] | | |] | | | | | |1125| |[pic|4 |0 |-6 |[pic|0 |0 | | | | | |] | | | |] | | | | |45|[pic|14|0 |[pic|1 |-1 |[pic|[pic|0 |Все [pic] | | |] | | |] | | |] |] | | | |30|[pic|22|1 |[pic|0 |2 |[pic|[pic|0 | | | |] | | |] | | |] |] | | | |0 |[pic|8 |0 |[pic|0 |-2 |[pic|[pic|1 | | | |] | | |] | | |] |] | | | | |1290| |0 |7 |0 |9 |6 |3 |0 | | При этом каждый элемент симплексной таблицы имеет определенный экономический смысл. Например, во второй симплексной таблице: |В столбце [pic]: | |[pic] |Показывает, на сколько следует уменьшить | | |изготовление изделия третьего вида, если | | |запланирован выпуск одного изделия первого | | |вида. | |[pic]; 3 |Показывают, сколько потребуется сырья второго и| | |третьего вида, при включении в план одного | | |изделия первого вида. | |Т.е. при включении в план одного изделия первого вида, потребуется | |уменьшение выпуска продукции третьего вида на 0.5 единиц, а также | |потребуются дополнительные затраты 2.5 единиц сырья второго вида и 3| |единицы сырья третьего вида, что приведет к увеличению прибыли | |предприятия на 7.5 денежных единиц. | |В столбце [pic]: | |[pic];[pic];[pic] |Показывают, что увеличение объема сырья первого | | |вида на единицу позволило бы увеличить выпуск | | |продукции третьего вида на[pic]. | | |[pic] | | |что одновременно потребовало бы [pic] единицы | | |сырья второго вида и [pic] единицы сырья | | |третьего вида. | Т.к. в последней строке третьей таблицы 1 нет ни одного отрицательного относительного оценочного коэффициента, то производственная программа, при которой получаемая предприятием прибыль имеет наибольшее значение, найдена, т.к., например, коэффициент [pic] при переменной [pic] показывает, что если произвести одну единицу продукции второго вида, то прибыль уменьшится на 7 денежных единиц. Таким образом, получили производственную программу: [pic], [pic], [pic], [pic] которая является оптимальной и обеспечивает предприятию наибольшую возможную прибыль: [pic] При этом первый и второй ресурсы будут использованы полностью, т.е. первый и второй ресурсы образуют «узкие места производства»: [pic], [pic] а третий ресурс будет иметь остаток: [pic] Помимо этого в третьей симплексной таблице получен обращенный базис, отвечающий оптимальной производственной программе: [pic] тогда можно проверить выполнение соотношения [pic]: [pic] а т.к. из третьей симплексной таблицы: [pic], следовательно, соотношение [pic] выполняется. 2. Двойственная задача Задача, двойственная линейной производственной задаче, например, может заключаться в оценке выгоды от продажи сырья, используемого в производстве, на сторону. Например, в предыдущем п.1. рассмотрена линейная производственная задача по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям. Предположим, некий предприниматель, занимающийся производством других видов продукции с использованием трех таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить y1 денежных единиц за каждую единицу первого ресурса, y2 денежных единиц за каждую единицу второго ресурса и y3 денежных единиц за каждую единицу третьего ресурса. Возникает вопрос: при каких значениях y1, y2, y3 можно согласиться с предложением этого предпринимателя. Т.к. в предыдущей задаче технологическая матрица [pic] затрат любого ресурса на единицу каждой продукции, вектор [pic] объемов ресурсов и вектор [pic] удельной прибыли имели вид: [pic] [pic] [pic] значит, для производства, например, первого вида продукции, предприятие должно затратить 3 единицы ресурса первого вида, 4 единицы ресурса второго вида и 4 единицы ресурса третьего вида, за что оно получит прибыль 30 денежных единиц. Следовательно, согласиться с предложением предпринимателя можно, если он заплатит не меньше, т.е. в ценах y1, y2, y3 это условие будет иметь вид: [pic] Аналогично и с продукцией второго, третьего и четвертого вида, при этом, за все имеющиеся ресурсы, предприниматель должен заплатить не меньше: [pic] денежных единиц. Следовательно, предприниматель будет искать такие значения y1, y2, y3, при которых эта сумма была бы как можно меньше. При этом речь идет о ценах, которые зависят не от цен по которым эти ресурсы были когда-то приобретены, а о ценах зависящих от применяемых в производстве технологий, объемов ресурсов и прибыли, которую возможно получить за произведенную продукцию. Таким образом, задача определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок [pic] минимизирующий общую оценку всех ресурсов [pic] при условии, что по каждому виду продукции суммарная оценка всех ресурсов, затрачиваемых на производство единицы продукции, не меньше прибыли, получаемой от реализации единицы этой продукции, т.е.: [pic] причем оценки ресурсов не могут быть отрицательными, т.е.: [pic], [pic], [pic] Решение полученной задачи можно найти с помощью второй теоремы двойственности: дефицитный (избыточный) ресурс, полностью (неполностью) используемый по оптимальному плану производства, имеет положительную (нулевую) оценку, и технология, применяемая с ненулевой (нулевой) интенсивностью, имеет нулевую (положительную) оценку. Т.е. для оптимальных решений [pic] и [pic] пары двойственных задач необходимо и достаточно выполнение условий: [pic] [pic] Ранее в п.1. было найдено, что [pic], [pic], а [pic] и [pic], тогда: [pic] Но т.к. третий ресурс был избыточным (см. п.1.), то по второй теореме двойственности, его двойственная оценка равна нулю, т.е. [pic]. Тогда переходим к новой системе уравнений: [pic] от куда получаем: [pic], [pic] Таким образом, получили двойственные оценки ресурсов: [pic], [pic], [pic] тогда общая оценка всех ресурсов равна: [pic] То же самое решение значений двойственных оценок содержится в последней строке симплексной таблицы 1 и имеет определенный экономический смысл: |[pic] |Показывает, что добавление одной единицы первого ресурса | |
|
© 2007 |
|