Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Учреждение образования
БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ
Факультет информационных технологий и управления
Кафедра информационных технологий автоматизированных систем
РАСЧЕТНО-ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
по курсу “Системный анализ и исследование операций”
на тему “Решение задачи линейного программирования”
Выполнила студент гр. 920604 __________Мыслейко К.В.
Руководитель __________Тиханович Т.В.
Минск 2011
СОДЕРЖАНИЕ
|
[1]
[2]
[3]
[4] [5] 5. Анализ базовой аналитической модели на чувствительность [5.1] 5.1 Статус и ценность ресурсов [5.2] 5.2 Анализ на чувствительность к изменениям коэффициентов целевой функции [5.3] 5.3 Анализ на чувствительность к изменению максимально возможного количества продаж нефтепродуктов.
[5.4] [6] 6. ОПТИМИЗАЦИЯ РЕШЕНИЯ НА ОСНОВЕ МОДИФИЦИРОВАННОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ [7] ЗАКЛЮЧЕНИЕ
[8]
[9] [9.1] 7.1 Пример 1 [9.2] 7.2 Пример 2 [10] ПРИЛОЖЕНИЕ А [11] ПРИЛОЖЕНИЕ Б [12] ПРИЛОЖЕНИЕ В
[13] |
ВВЕДЕНИЕ
Исследованием операций называется специальная наука, занимающаяся рациональными способами организации целенаправленной человеческой деятельности. Методы исследования операций применяются в самых разных областях: в промышленности, торговле, на транспорте, в медицине, городском и сельском хозяйстве, военном деле – одним словом, везде, где приходится организовывать какие-то мероприятия, направленные к достижению определенной цели. Очевидно, организовывать их следует так, чтобы они наилучшим образом способствовали достижению поставленной цели, т.е. были максимально эффективными.
В исследовании операций нет единого метода решения всех математических моделей, которые встречаются на практике. Вместо этого выбор метода решения диктуют тип и сложность исследуемой математической модели.
Наиболее эффективными и известными методами исследования операций являются методы:
а) линейного программирования, когда целевая функция и все ограничения являются линейными функциями
б) методы целочисленного программирования (если все переменные должны принимать только целочисленные значения)
в) методы динамического программирования (где исходную задачу можно разбить на меньшие подзадачи)
г) методы нелинейного программирования (когда целевая функция и/или ограничения являются нелинейными функциями)
д) методы исследования функций классического анализа
е) методы, основанные на использовании неопределенных множителей Лагранжа
ж) вариационное исчисление
к) принцип максимума
л) метод геометрического программирования
Как правило, нельзя рекомендовать какой-либо один метод, который можно использовать для решения всех без исключения задач, возникающих на практике. Одни методы в этом отношении являются более общими, другие - менее общими.
Ниже приведена краткая характеристика указанных методов и областей их применения, что до некоторой степени может облегчить выбор того или иного метода для решения конкретной оптимальной задачи.
Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Такие задачи обычно встречаются при решении вопросов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана перевозок (транспортные задачи) и т. д.
Для решения большого круга задач линейного программирования имеется практически универсальный алгоритм - симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи.
Динамическое программирование служит эффективным методом решения задач оптимизации дискретных многостадийных процессов, для которых критерий оптимальности задается как аддитивная функция критериев оптимальности отдельных стадий. Без особых затруднений указанный метод можно распространить и на случай, когда критерий оптимальности задан в другой форме, однако при этом обычно увеличивается размерность отдельных стадий.
По существу метод динамического программирования представляет собой алгоритм определения оптимальной стратегии управления на всех стадиях процесса. При этом закон управления на каждой стадии находят путем решения частных задач оптимизации последовательно для всех стадий процесса с помощью методов исследования функций классического анализа или методов нелинейного программирования. Результаты решения обычно не могут быть выражены в аналитической форме, а получаются в виде таблиц.
Ограничения на переменные задачи не оказывают влияния на общий алгоритм решения, а учитываются при решении частных задач оптимизации на каждой стадии процесса. При наличии ограничений типа равенств иногда даже удается снизить размерность этих частных задач за счет использования множителей Лагранжа. Применение метода динамического программирования для оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации приводит к решению дифференциальных уравнений в частных производных. Вместо решения таких уравнений зачастую значительно проще представить непрерывный процесс как дискретный с достаточно большим числом стадий. Подобный прием оправдан особенно в тех случаях, когда имеются ограничения на переменные задачи и прямое решение дифференциальных уравнений осложняется необходимостью учета указанных ограничений.
При решении задач методом динамического программирования, как правило, используют вычислительные машины, обладающие достаточным объемом памяти для хранения промежуточных результатов решения, которые обычно получаются в табличной форме.
Методы нелинейного программирования применяют для решения оптимальных задач с нелинейными функциями цели. На независимые переменные могут быть наложены ограничения также в виде нелинейных соотношений, имеющих вид равенств или неравенств. По существу методы нелинейного программирования используют, если ни один из перечисленных выше методов не позволяет сколько-нибудь продвинуться в решении оптимальной задачи. Поэтому указанные методы иногда называют также прямыми методами решения оптимальных задач.
Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип максимума и т. п. на определенных этапах их применения.
Названием “методы нелинейного программирования” объединяется большая группа численных методов, многие из которых приспособлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного программирования практически постоянно используется в сочетании с другими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.
Методы исследования функций классического анализа представляют собой наиболее известные методы решения несложных оптимальных задач, с которыми известны из курса математического анализа. Обычной областью использования данных методов являются задачи с известным аналитическим выражением критерия оптимальности, что позволяет найти не очень сложное, также аналитическое выражение для производных. Полученные приравниванием нулю производных уравнения, определяющие экстремальные решения оптимальной задачи, крайне редко удается решить аналитическим путем, поэтому, как, правило, применяют вычислительные машины. При этом надо решить систему конечных уравнений, чаще всего нелинейных, для чего приходится использовать численные методы, аналогичные методам нелинейного программирования.
Дополнительные трудности при решении оптимальной задачи методами исследования функций классического анализа возникают вследствие того, что система уравнений, получаемая в результате их применения, обеспечивает лишь необходимые условия оптимальности. Поэтому все решения данной системы (а их может быть и несколько) должны быть проверены на достаточность. В результате такой проверки сначала отбрасывают решения, которые не определяют экстремальные значения критерия оптимальности, а затем среди остающихся экстремальных решений выбирают решение, удовлетворяющее условиям оптимальной задачи, т. е. наибольшему или наименьшему значению критерия оптимальности в зависимости от постановки задачи.
Методы исследования при наличии ограничений на область изменения независимых переменных можно использовать только для отыскания экстремальных значений внутри указанной области. В особенности это относится к задачам с большим числом независимых переменных (практически больше двух), в которых анализ значений критерия оптимальности на границе допустимой области изменения переменных становится весьма сложным.
Метод множителей Лагранжа применяют для решения задач такого же класса сложности, как и при использовании обычных методов исследования функций, но при наличии ограничений типа равенств на независимые переменные. К требованию возможности получения аналитических выражений для производных от критерия оптимальности при этом добавляется аналогичное требование относительно аналитического вида уравнений ограничений.
В основном при использовании метода множителей Лагранжа приходится решать те же задачи, что и без ограничений. Некоторое усложнение в данном случае возникает лишь от введения дополнительных неопределенных множителей, вследствие чего порядок системы уравнений, решаемой для нахождения экстремумов критерия оптимальности, соответственно повышается на число ограничений. В остальном, процедура поиска решений и проверки их на оптимальность отвечает процедуре решения задач без ограничений.
Множители Лагранжа можно применять для решения задач оптимизации объектов на основе уравнений с частными производными и задач динамической оптимизации. При этом вместо решения системы конечных уравнений для отыскания оптимума необходимо интегрировать систему дифференциальных уравнений.
Следует отметить, что множители Лагранжа используют также в качестве вспомогательного средства и при решении специальными методами задач других классов с ограничениями типа равенств, например, в вариационном исчислении и динамическом программировании. Особенно эффективно применение множителей Лагранжа в методе динамического программирования, где с их помощью иногда удается снизить размерность решаемой задачи.
Методы вариационного исчисления обычно используют для решения задач, в которых критерии оптимальности представляются в виде функционалов и решениями которых служат неизвестные функции. Такие задачи возникают обычно при статической оптимизации процессов с распределенными параметрами или в задачах динамической оптимизации.
Вариационные методы позволяют в этом случае свести решение оптимальной задачи к интегрированию системы дифференциальных уравнений Эйлера, каждое из которых является нелинейным дифференциальным уравнением второго порядка с граничными условиями, заданными на обоих концах интервала интегрирования. Число уравнений указанной системы при этом равно числу неизвестных функций, определяемых при решении оптимальной задачи. Каждую функцию находят в результате интегрирования получаемой системы.
Уравнения Эйлера выводятся как необходимые условия экстремума функционала. Поэтому полученные интегрированием системы дифференциальных уравнений функции должны быть проверены на экстремум функционала
При наличии ограничений типа равенств, имеющих вид функционалов, применяют множители Лагранжа, что дает возможность перейти от условной задачи к безусловной. Наиболее значительные трудности при использовании вариационных методов возникают в случае решения задач с ограничениями типа неравенств.
Заслуживают внимания прямые методы решения задач оптимизации функционалов, обычно позволяющие свести исходную вариационную задачу к задаче нелинейного программирования, решить которую иногда проще, чем краевую задачу для уравнений Эйлера.
Принцип максимума применяют для решения задач оптимизации процессов, описываемых системами дифференциальных уравнений. Достоинством математического аппарата принципа максимума является то, что решение может определяться в виде разрывных функций; это свойственно многим задачам оптимизации, например задачам оптимального управления объектами, описываемыми линейными дифференциальными уравнениями.
Нахождение оптимального решения при использовании принципа максимума сводится к задаче интегрирования системы дифференциальных уравнений процесса и сопряженной системы для вспомогательных функций при граничных условиях, заданных на обоих концах интервала интегрирования, т. е. к решению краевой задачи. На область изменения переменных могут быть наложены ограничения. Систему дифференциальных уравнений интегрируют, применяя обычные программы на цифровых вычислительных машинах.
Принцип максимума для процессов, описываемых дифференциальными уравнениями, при некоторых предположениях является достаточным условием оптимальности. Поэтому дополнительной проверки на оптимум получаемых решений обычно не требуется.
Для дискретных процессов принцип максимума в той же формулировке, что и для непрерывных, вообще говоря, несправедлив. Однако условия оптимальности, получаемые при его применении для многостадийных процессов, позволяют найти достаточно удобные алгоритмы оптимизации.
Геометрическое программирование есть метод решения одного специального класса задач нелинейного программирования, в которых критерий оптимальности и ограничения задаются в виде позиномов - выражений, представляющих собой сумму произведений степенных функций от независимых переменных. С подобными задачами иногда приходится сталкиваться в проектировании. Кроме того, некоторые задачи нелинейного программирования иногда можно свести к указанному представлению, используя аппроксимационное представление для целевых функций и ограничений.
Практически все методы исследования операций не позволяют получить решение в замкнутой (в виде формул) форме. Напротив, они порождают значительные алгоритмы, которые являются итерационными по своей природе. Это означает, что задача решается последовательно (итерационно), когда на каждом шаге (итерации) получаем решения, постепенно сходящиеся к оптимальному. Итерационная природа алгоритмов обычно приводит к объемным однотипным вычислениям. В этом и заключается причина того, что эти алгоритмы разрабатываются, в основном, для реализации с помощью вычислительной техники.
Некоторые математические модели могут быть такими сложными, что их невозможно решить никакими доступными методами оптимизации. В этом случае остается только эвристический подход: поиск подходящего «хорошего» решения вместо оптимального. Эвристический подход предполагает наличие эмпирических правил, в соответствии с которыми ведется поиск подходящего решения.
Нефтеперерабатывающее предприятие выпускает нефтепродукты четырех видов: дизельное топливо, бензин, смазочные материал и авиационное топливо. Спрос на эти виды продукции не превышает соответственно 14, 30, 10 и 8 тыс. баррелей в день.
Для производства нефтепродуктов используется нефть двух сортов (Н1 и Н2). Стоимость одного барреля нефти Н1 составляет 40 ден.ед., нефти Н2 – 51 ден.ед. В общем объеме нефти, используемой предприятием, нефть Н1 составляет не менее 40%.
Количество нефтепродуктов (в баррелях), получаемых из одного барреля нефти каждого вида, приведено в таблице.
|
Сорт нефти |
Дизельное топливо |
Бензин |
Смазочные материалы |
Авиационное топливо |
|
H1 |
0,2 |
0,25 |
0,1 |
0,15 |
|
H2 |
0,1 |
0,6 |
0,15 |
0,1 |
Стоимость одного барреля дизельного топлива – 55 ден.ед., бензина – 60 ден.ед., смазочных материалов – 50 ден.ед, авиационного топлива – 70 ден.ед.
Найти, сколько нефти каждого сорта следует переработать, чтобы получить максимальную прибыль от выпуска нефтепродуктов.
В данной задаче необходимо составить план распределения нефти для получения максимальной прибыли от выпуска нефтепродуктов.
Для построения математической модели задачи введем переменные. Обозначим:
х1 – количество нефти H1 (в баррелях);
х2 – количество нефти H2 (в баррелях).
Составим целевую функцию:
Здесь:
– прибыль от продаж нефтепродуктов, получаемых из нефти вида H1;
– прибыль от продаж нефтепродуктов, получаемых из нефти вида H2.
Необходимо обеспечить максимальную прибыль от выпуска нефтепродуктов, следовательно, целевая функция стремится к максимуму.
Составим все возможные ограничения данной задачи.
Спрос на дизельное топливо, бензин, смазочные материалы, авиационное топливо, не превышает 14, 30, 10 и 8 тыс. баррелей в день. Следовательно, получим следующие ограничения:
;
;
;
.
Объеме нефти, используемой предприятием, нефть Н1 составляет не менее 40%.
Получим следующее ограничение:
.
Приведем полную математическую модель рассматриваемой задачи:
В данной задаче переменные по своему физическому смыслу не могут быть отрицательными. Поэтому на них накладывается ограничение неотрицательности.
Все ограничения и целевая функция в данной задаче линейны, поэтому для ее решения можно использовать симплекс-метод. В математической модели задачи есть ограничения «больше или равно», поэтому требуется использовать метод искусственного базиса (двухэтапный метод).
Приведем математическую модель задачи к стандартной форме. Для этого в ограничения «меньше или равно» добавим остаточные переменные, в ограничения «больше или равно» вводим избыточные переменные, а в ограничение «равно» не требуется вводить никаких дополнительных переменных.
В ограничении отсутствует базисная переменная (т.е. переменная, входящая только в данное ограничение с коэффициентом равным единицы). Поэтому требуется ввести искусственную переменную:
Таким образом, в каждом ограничении имеется базисная переменная (, , , и ). Остальные переменные – небазисные.
Составим искусственную целевую функцию – сумму всех искусственных переменных:
.
Далее искусственная целевая функция выражается через небазисные переменные. Для этого сначала выразим искусственную переменную через небазисные переменные:
.
Выраженную искусственную переменную подставим в целевую функцию:
.
Для приведения всей задачи к стандартной форме выполняем переход к искусственной целевой функции, подлежащей максимизации. Для этого умножаем её на -1:
Составим первую симплекс таблицу (таблица 4.2).
Таблица 4.2
|
Базис |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Х7 |
Х8 |
Решение |
|
E |
-1,5 |
-5 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
-W |
-0,6 |
0,4 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
X8 |
0,6 |
-0,4 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X4 |
0,2 |
0,1 |
0 |
1 |
0 |
0 |
0 |
0 |
14000 |
|
X5 |
0,25 |
0,6 |
0 |
0 |
1 |
0 |
0 |
0 |
30000 |
|
X6 |
0,1 |
0,15 |
0 |
0 |
0 |
1 |
0 |
0 |
10000 |
|
X7 |
0,15 |
0,1 |
0 |
0 |
0 |
0 |
1 |
0 |
8000 |
Определяем начальное решение. Все исходные, а также избыточные переменные принимаются равными нулю. Искусственные, а также остаточные переменные равны правым частям ограничений, т.е , ,,,,.
Это решение является недопустимым, т.к. не удовлетворяют поставленной задаче.
Начальное значение целевой функции равно нулю. Начальное значение искусственной целевой функции равно нулю.
В первой строке перечислены все переменные (исходные и дополнительные), в первой колонке – переменные входящие в базис, в строке целевой функции и искусственной целевой функции указываются коэффициенты ограничений с обратным знаком, в которые входят эти переменные.
Определим переменную для включения в базис. В нашей задаче необходимо включить в базис переменную X1, т.к. ей соответствует максимальный по модулю отрицательный коэффициент в строке искусственной целевой функции. Определим переменную для исключения из базиса. Для этого найдем симплекс-отношения:0/0,60=0; 14000/1=14000; 30000/0,25=120000; 10000/0,10=100000; 8000/0,15=53333;3. Минимальное симплексное отношение получено для строки, соответствующей базисной переменной X8, значит, эта переменная исключается из базиса, то есть становится равной нулю. Минимальное отношение показывает, что при увеличении X1 переменная X8 первая достигнет нуля.
Выполним пересчет исходной симплекс-таблицы:
Таблица 4.3
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
Решение |
|
E |
0 |
-6 |
-2,5 |
0 |
0 |
0 |
0 |
2,5 |
0 |
|
-W |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
X1 |
1 |
-0,67 |
-1,67 |
0 |
0 |
0 |
0 |
1,67 |
0 |
|
X4 |
0 |
0,23 |
0,33 |
1 |
0 |
0 |
0 |
-0,33 |
14000 |
|
X5 |
0 |
0,77 |
0,42 |
0 |
1 |
0 |
0 |
-0,42 |
30000 |
|
X6 |
0 |
0,22 |
0,17 |
0 |
0 |
1 |
0 |
-0,17 |
10000 |
|
X7 |
0 |
0,2 |
0,25 |
0 |
0 |
0 |
1 |
-0,25 |
8000 |
Как видно из табл. 4.3, искусственная целевая функция равна нулю, и все искусственные переменные исключены из базиса. Получено допустимое решение. Далее искусственная целевая функция и искусственные переменные исключаются из симплекс-таблицы :
Таблица 4.4
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
Е |
0 |
-4 |
-2,5 |
0 |
0 |
0 |
0 |
0 |
|
Х1 |
1 |
0,67 |
-1,67 |
0 |
0 |
0 |
0 |
0 |
|
Х4 |
0 |
-0,03 |
0,33 |
1 |
0 |
0 |
0 |
14000 |
|
X5 |
0 |
0,43 |
0,42 |
0 |
1 |
0 |
0 |
30000 |
|
X6 |
0 |
0,08 |
0,17 |
0 |
0 |
1 |
0 |
10000 |
|
X7 |
0 |
0 |
0,25 |
0 |
0 |
0 |
1 |
8000 |
Данное решение не является оптимальным, т.к. в строке целевой функции имеются отрицательные элементы. Поиск оптимального решения выполняется по обычным правилам симплекс-метода. В базис включается переменная X2. Найдем симплекс-отношения: 0/0,67=0; 14000/-0,03=-466666,6; 30000/0,43=69767,4; 10000/0,08=125000; 8000/0=∞. Из базиса исключается переменная X5. После преобразований по правилам симплекс-метода получим новую симплекс-таблицу:
Таблица 4.5
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
E |
6 |
0 |
-12,5 |
0 |
0 |
0 |
0 |
0 |
|
X2 |
1,5 |
1 |
-2,5 |
0 |
0 |
0 |
0 |
0 |
|
X4 |
0,05 |
0 |
0,25 |
1 |
0 |
0 |
0 |
14000 |
|
X5 |
-0,65 |
0 |
1,5 |
0 |
1 |
0 |
0 |
30000 |
|
X6 |
-0,12 |
0 |
0,37 |
0 |
0 |
1 |
0 |
10000 |
|
X7 |
0 |
0 |
0,25 |
0 |
0 |
0 |
1 |
8000 |
Полученное решение не является оптимальным: в целевой функции остались отрицательные переменные.
Совершим еще одно преобразование таблицы. В этот раз переменной для включения в базис становиться X3. Вновь найдем симплекс-отношения: 0/-2,5=0; 14000/0,25=56000; 30000/1,5=20000; 10000/0,37=27027,02; 8000/0,25=32000.
Таблица 4.6
|
Базис |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
Решение |
|
E |
0,58 |
0 |
0 |
0 |
8,33 |
0 |
0 |
250000 |
|
X2 |
0,42 |
1 |
0 |
0 |
1,67 |
0 |
0 |
50000 |
|
X4 |
0,16 |
0 |
0 |
1 |
-0,17 |
0 |
0 |
9000 |
|
X3 |
-0,43 |
0 |
1 |
0 |
0,67 |
0 |
0 |
20000 |
|
X6 |
0,04 |
0 |
0 |
0 |
-0,25 |
1 |
0 |
2500 |
|
X7 |
0,11 |
0 |
0 |
0 |
-0,17 |
0 |
1 |
3000 |
Получено оптимальное решение. Основные переменные приняли значения: X1=0, X2=50000. Это означает, что для максимизации прибыли от нефтесодержащих продуктов необходимо закупать 50 тыс. баррелей нефти вила H2,закупка вида H1 не выгодна.
Остаточные переменные Х4=9 тыс., Х5=0, Х6=2,5 тыс. и Х7=3 тыс., это означает что при реализации дизельного топлива осталось неизрасходованным 9 тыс. баррелей, при реализации смазочного материала - 2,5 тыс. баррелей, а при реализации авиационного топлива – 3 тыс. баррелей, при этом бензин реализуется полностью.
Избыточная переменная Х3=20 тыс. баррелей означает, что использование в производстве нефти вида Н1 превышает минимально необходимое количество на 20 тыс. баррелей. Решение данной задачи представлено в приложении А.
В данной задаче ресурсами являются дизельное топливо, бензин, смазочные материалы и авиационное топливо.
Как видно из значений остаточных переменных, что при реализации дизельного топлива осталось неизрасходованным 9 тыс. баррелей, при реализации смазочного материала - 2,5 тыс. баррелей, а при реализации авиационного топлива – 3 тыс. баррелей, то есть они являются не дефицитными ресурсами. Увеличение объема продуктов, изготовленных из нефти вида Н1 и Н2 является не целесообразно: оно приведет только к увеличению неизрасходованного остатка.
При этом бензин израсходован полностью, т.е. он является дефицитным ресурсом. Увеличение поставок приведет к увеличению прибыли; снижение поставок приведет к снижению прибыли.
Ценности ресурсов представляет собой коэффициенты Е-строки при остаточных переменных, соответствующих остаткам ресурсов, в симплекс таблице с оптимальным решением.(таблица 4.7). Ценность бензина составляет 8,33 тыс. ден.ед, а ценность дизельного топлива, авиационного топлива и смазочного материала равна нулю. Это означает, что увеличение количества бензина на 1 тыс. баррелей, приведет к увеличению прибыли в среднем на 8,33 тыс. ден.ед. Нулевое значение ценности означает, что увеличение количества этих продуктов или их снижение не приведет к изменению прибыли, т.к. данные продукты не дефицитны.
Пусть прибыль от продажи одного продукта из нефти вида Н2 (X1) изменится на d единиц и составит 310+d. Если изменение прибыли не выходит за некоторый диапазон значений, то новые значения коэффициентов Е-строки при небазисных переменных для окончательной симплекс-таблицы, а также новое значение целевой функции можно найти следующим образом:
Значения 0,42, 1,67 и 50000 взяты из строки переменной X2 окончательной симплекс-таблицы. Здесь F1 и F5 – новые значения коэффициентов Е-строки при небазисных переменных в окончательной симплекс-таблице.
Также можно рассчитать диапазон изменений прибыли, при котором решение остается оптимальным:
В результате решения системы получим диапазон изменения прибыли:
≥ -4,9.
Это означает, что найденное для задачи решение оптимально, если прибыль от использования нефти вида Н1 будет составлять не менее 310,8-4,9 = 305,9 ден.ед.
Для этого будем использовать коэффициенты из столбца остаточной переменной, входящей в изменившееся ограничение.
Пусть максимально возможное количество бензина изменилось на d и составляет не 30000, а 30000+d (X5). Новое оптимальное решение можно найти следующим образом:
Коэффициенты при d взяты из столбца переменной X5 в окончательной симплекс-таблице. Соответственно новое решение, возможно высчитать, подставив в систему разность между имеющимся количеством ресурсов и высчитанным.
Также можно определить диапазон изменений ресурса, при котором состав переменных в оптимальном базисе остается прежним:
Решив эту систему неравенств, получим диапазон:
-29850 ≤ d ≤ 10000.
Это означает, что найденное для задачи решение оптимально, если максимально возможное количество будет составлять не менее 150 и не более 40000 баррелей.
Для этого будем использовать коэффициенты из столбца избыточной переменной, входящей в изменившееся ограничение, взятые с обратным знаком.
Пусть минимальное количество сырья изменилось на d и составляет не 0, а 0+d (X3). Новое оптимальное решение можно найти следующим образом:
Коэффициенты 0, 0, 1, 0, 0, 0, взяты из столбца переменной X3 в окончательной симплекс-таблице. Соответственно новое решение, возможно высчитать, подставив в систему разность между новым количеством сырья и минимальным.
Также можно определить диапазон изменений количества сырья, при котором состав переменных в оптимальном базисе остается прежним:
Решив эту систему неравенств, получим диапазон:
d ≤ 20000.
Это означает, что найденное для задачи решение оптимально, если минимально необходимое количество лисиц будет составлять не более 20 тыс. баррелей.
Проанализировав результаты решения задачи оптимизации, можно сделать следующие выводы:
В зависимости от конкретных условий зверофермы эти недостатки могут быть устранены.
Так как мы имеем высокий спрос на бензин, то большая часть нефти тратится на его производство, из-за этого не хватает сырья для производства сырья другой продукции. Так как мы на прямую не можем управлять спросом, то максимизируем нашу прибыль увеличением цены стоимости бензина в пределах 10%.Увеличим стоимость бензина на 6 ден. ед., с учетом затрат получаем систему:
В результате решения данной системы получим прибыль в 430 тыс. ден. ед. Значение остаточных переменных не изменилось.
Оптимальное решение будет следующим: Х1=0, Х2=50000, Х3=0, Х4=9000, Х5=0, Х6=2500, Х7=3000, Е=430 000.
Сравнительная характеристика двух планов работы зверофермы (при базовом и новом варианте количества клеток) приведена в таблице 9.
Таблица 9
|
Показатели |
Базовый вариант |
Новый вариант |
|
Количество нефти, тыс. баррелей H1 H2 |
0 50 |
0 50 |
|
Остатки спроса, тыс. баррелей Дизельное топливо Бензин Смазочные материалы Авиационное топливо |
9 0 2,5 3 |
9 0 2,5 3 |
|
Прибыль, тыс. ден. ед. |
250 |
430 |
Видно, что увеличение цены на бензин позволяет существенно улучшить показатели. Увеличена прибыль на 180 тыс. ден. ед. Решение данной задачи представлено в приложении Б.
Основные переменные приняли следующие значения: х1=0, х2=50000. Это означает, что для получения максимальной прибыли приданных условиях необходимо потратить сырья Н2 в размере 50 тыс. баррелей, сырье Н1 не используется.
Значение целевой функции Е=250 000 показывает, что при таком распределении, прибыль от продажи окажется равной 250 с ден.ед.
Избыточная переменная х3=20000 означает, что количество используемого сырья Н2 будет на 20 тыс. единиц больше минимально запланированного.
Остаточная переменная х4=9 тыс. показывает, что количество выпущенного дизельного топлива будет на 9 тыс. единиц меньше максимально возможного.
Остаточная переменная х5=0 показывает, что количество выпущенного бензина будет равно максимальному значению .
Остаточная переменная х6=2500 показывает, что количество выпущенных смазочных материалов будет на 2,5 тыс. баррелей меньше максимально возможного.
Остаточная переменная х7=3000 показывает, что количество выпущенного авиационного топлива будет на 3 тыс. баррелей меньше максимально возможного.
В результате проведения модификации задачи было выявлено, что не весь спрос удовлетворяется, но так как мы ничего не можем с этим поделать, будем увеличивать прибыль путем увеличения стоимости бензина. Эту проблему можно решить увеличив количество клеток.
На поле площадью 500 км2 можно выращивать три вида культур: рожь, пшеница и ячмень. Характеристики этих культур приведены в таблице 10.
Таблица 10
|
Культура |
Цена, тыс. ден. ед. |
Урожайность, т/км2 |
Расход удобрений на 1 км2, кг |
|
|
калийные |
фосфаты |
|||
|
Пшеница |
50 |
20 |
20 |
5 |
|
Рожь |
200 |
15 |
15 |
10 |
|
Ячмень |
100 |
60 |
10 |
10 |
Максимальное количество калийных удобрений, которое можно использовать 200 кг, а фосфатов – 100 кг.
Требуется разработать план посева зерновых, позволяющий получать максимальную прибыль.
Для построения математической модели задачи введем переменные. Обозначим:
х1 – площадь, занимаемая Пшеница (км2);
х2 – площадь, занимаемая Рожь (км2);
х3 – площадь, занимаемая Ячмень (км2).
Приведем полную математическую модель рассматриваемой задачи:
В данной задаче переменные по своему физическому смыслу не могут быть отрицательными. Поэтому на них накладывается ограничение неотрицательности.
Приведем математическую модель задачи к стандартной форме. Для этого в ограничения «меньше или равно» добавим остаточные переменные:
Решив задачу симплекс-методом, получим: X1=0, X2=0, X3=10 при доходе 60000 денежных единиц. Решение данной задачи представлено в приложении В.
В собственности фирмы имеется два магазина. Исходные данные представлены в таблице 11.
|
Магазин |
Количество вырученной продукции, единиц/день |
|
|
одежда |
обувь |
|
|
1 |
50 |
20 |
|
2 |
40 |
30 |
Каждый магазин работает не более 30 дней. Поставщики могут поставить не более 4400 единиц одежды в месяц и не более 3000 единиц обуви.
Прибыль от продажи одной единицы одежды составляет 4 ден. ед., а от одной единицы обуви – 10 ден. ед.
Составить план работы фирмы, обеспечивающий максимальную прибыль.
Для построения математической модели задачи введем переменные. Обозначим:
х1 – время работы первого магазина (день);
х2 – время работы второго магазина (день).
Приведем полную математическую модель рассматриваемой задачи:
В данной задаче переменные по своему физическому смыслу не могут быть отрицательными. Поэтому на них накладывается ограничение неотрицательности.
Приведем математическую модель задачи к стандартной форме. Для этого в ограничения «меньше или равно» добавим остаточные переменные:
Решив задачу симплекс-методом, получим: X1=30, X2=30 при доходе 25800 денежных единиц. Решение данной задачи представлено в приложении Г.
(справочное)
ПРОТОКОЛ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ MS EXCEL
(справочное)
РАБОЧИЙ ЛИСТ MS EXCEL С РЕЗУЛЬТАТАМИ ОПТИМИЗАЦИИ
НА ОСНОВЕ МОДИФИЦИРОВАННОЙ АНАЛИТИЧЕСКОЙ МОДЕЛИ
ПРОТОКОЛ РЕШЕНИЯ ПЕРСПЕКТИВНОЙ ОПТИМИЗАЦИОННОЙ
УПРАВЛЕНЧЕСКОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ MS EXCEL
ПРОТОКОЛ РЕШЕНИЯ ПЕРСПЕКТИВНОЙ ОПТИМИЗАЦИОННОЙ
УПРАВЛЕНЧЕСКОЙ ЗАДАЧИ С ИСПОЛЬЗОВАНИЕМ MS EXCEL