Курсовая работа по дисциплине «Системный анализ и исследование операций»




Скачать 279.15 Kb.
НазваниеКурсовая работа по дисциплине «Системный анализ и исследование операций»
страница1/2
Дата публикации13.02.2014
Размер279.15 Kb.
ТипКурсовая
uchebilka.ru > Информатика > Курсовая
  1   2
Реферат скачан с сайта allreferat.wow.ua


Решение оптимизационной задачи линейного программирования

Белорусский государственный университет информатики и радиоэлектроники Факультет информационных технологий и управления Кафедра информационных технологий автоматизированных систем «К защите допускаю» ______________Н.В. Батин “___”______________2001г. КУРСОВАЯ РАБОТА по дисциплине «Системный анализ и исследование операций» на тему: «Решение оптимизационной задачи линейного программирования» Выполнил студент гр. 920603 ЖуравкинА.В. Руководитель работы БатинН.В. Минск, 2001 СОДЕРЖАНИЕ:ВВЕДЕНИЕ…….………………………………………………………………...31. Постановка задачи оптимизации……………………………………….…82. Построение аналитической модели…………………………………….…93. Обоснование и описание вычислительной процедуры………………..11 1. Приведение задачи линейного программирования к стандартной форме………………..………………………………………………….11 2. Основная идея симлекс-метода……………………………………..12 3. Двухэтапный симплекс-метод………………………………………124. Решение задачи оптимизации на основе симплекс-таблиц……………14 1. Приведение задачи к стандартной форме………..………………..14 2. Определение начального допустимого решения…………………14 3. Построение искусственного базиса………...………………………15 4. Первый этап двухэтапного симплекс-метода…………………….16 5. Второй этап двухэтапного метода………………………………….195. Анализ модели на чувствительность……………………………………..22 1. Статус ресурсов……….………………………………………………22 2. Ценность ресурсов……………………………………………………22 3. Анализ на чувствительность к изменениям правых частей ограничений……………………………………………………….…..23 4. Анализ на чувствительность к изменениям коэффициентов целевой функции……………………………………………...………256. Определение оптимального целочисленного решения…………………26 6.1. Метод Гомори для частично целочисленных задач……..……….26ЗАКЛЮЧЕНИЕ…………………………………………………………...……33СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….……..34УСЛОВНЫЕ СОКРАЩЕНИЯ………………………….……………………35ПРИЛОЖЕНИЕ…………………………………………………………….…..36 ВВЕДЕНИЕ В настоящее время оптимизация находит применение в науке, технике и влюбой другой области человеческой деятельности. Оптимизация - целенаправленная деятельность, заключающаяся в получениинаилучших результатов при соответствующих условиях. Поиски оптимальных решений привели к созданию специальныхматематических методов и уже в 18 веке были заложены математические основыоптимизации (вариационное исчисление, численные методы и др). Однако довторой половины 20 века методы оптимизации во многих областях науки итехники применялись очень редко, поскольку практическое использованиематематических методов оптимизации требовало огромной вычислительнойработы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев -невозможно. Постановка задачи оптимизации предполагает существование конкурирующихсвойств процесса, например: ( количество продукции - расход сырья ( количество продукции - качество продукции Выбор компромиcного варианта для указанных свойств и представляетсобой процедуру решения оптимизационной задачи. При постановке задачи оптимизации необходимо: 1. Наличие объекта оптимизации и цели оптимизации. При этомформулировка каждой задачи оптимизации должна требовать экстремальногозначения лишь одной величины, т.е. одновременно системе не должноприписываться два и более критериев оптимизации, т.к. практически всегдаэкстремум одного критерия не соответствует экстремуму другого. Приведемпримеры. Типичный пример неправильной постановки задачи оптимизации: «Получить максимальную производительность при минимальной себестоимости». Ошибка заключается в том, что ставится задача поиска оптимальности 2-хвеличин, противоречащих друг другу по своей сути. Правильная постановка задачи могла быть следующая: а) получить максимальную производительность при заданной себестоимости; б) получить минимальную себестоимость при заданной производительности; В первом случае критерий оптимизации - производительность а во втором- себестоимость. 2. Наличие ресурсов оптимизации, под которыми понимают возможностьвыбора значений некоторых параметров оптимизируемого объекта. 3. Возможность количественной оценки оптимизируемой величины,поскольку только в этом случае можно сравнивать эффекты от выбора тех илииных управляющих воздействий. 4. Учет ограничений. Обычно оптимизируемая величина связана с экономичностью работырассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариантработы объекта должен оцениваться какой-то количественной мерой - критериемоптимальности. Критерием оптимальности называется количественная оценкаоптимизируемого качества объекта. На основании выбранного критерия оптимальности составляется целеваяфункция, представляющая собой зависимость критерия оптимальности отпараметров, влияющих на ее значение. Вид критерия оптимальности или целевойфункции определяется конкретной задачей оптимизации. Таким образом, задача оптимизации сводится к нахождению экстремумацелевой функции. В зависимости от своей постановки, любая из задач оптимизации можетрешаться различными методами, и наоборот – любой метод может применятьсядля решения многих задач. Методы оптимизации могут быть скалярными(оптимизация проводится по одному критерию), векторными (оптимизацияпроводится по многим критериям), поисковыми (включают методы регулярного иметоды случайного поиска), аналитическими (методы дифференциальногоисчисления, методы вариационного исчисления и др.), вычислительными(основаны на математическом программировании, которое может быть линейным,нелинейным, дискретным, динамическим, стохастическим, эвристическим ит.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергатьсяоптимизации могут задачи как с ограничениями, так и без них. Линейное программирование - один из первых и наиболее подробноизученных разделов математического программирования. Именно линейноепрограммирование явилось тем разделом, с которого начала развиваться самадисциплина «математическое программирование». Термин «программирование» вназвании дисциплины ничего общего с термином «программирование (т.е.составление программ) для ЭВМ» не имеет, так как дисциплина «линейноепрограммирование» возникла еще до того времени, когда ЭВМ стали широкоприменяться при решении математических, инженерных, экономических и др.задач. Термин «линейное программирование» возник в результате неточногоперевода английского «linear programming». Одно из значений слова«programming» - составление планов, планирование. Следовательно, правильнымпереводом «linear programming» было бы не «линейное программирование», а«линейное планирование», что более точно отражает содержание дисциплины.Однако, термин линейное программирование, нелинейное программирование ит.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй МировойВойны и стал быстро развиваться, привлекая внимание математиков,экономистов и инженеров благодаря возможности широкого практическогоприменения, а так же математической «стройности». Можно сказать, что линейное программирование применимо дляпостроения математических моделей тех процессов, в основу которых можетбыть положена гипотеза линейного представления реального мира:экономических задач, задач управления и планирования, оптимальногоразмещения оборудования и пр. Задачами линейного программирования называются задачи, в которых линейныкак целевая функция, так и ограничения в виде равенств и неравенств. Краткозадачу линейного программирования можно сформулировать следующим образом:найти вектор значений переменных, доставляющих экстремум линейной целевойфункции при m ограничениях в виде линейных равенств или неравенств. Линейное программирование представляет собой наиболее частоиспользуемый метод оптимизации. К числу задач линейного программированияможно отнести задачи:рационального использования сырья и материалов; задачи оптимизации раскроя;оптимизации производственной программы предприятий;оптимального размещения и концентрации производства;составления оптимального плана перевозок, работы транспорта;управления производственными запасами;и многие другие, принадлежащие сфере оптимального планирования. Так, по оценкам американских экспертов, около 75% от общего числаприменяемых оптимизационных методов приходится на линейноепрограммирование. Около четверти машинного времени, затраченного впоследние годы на проведение научных исследований, было отведено решениюзадач линейного программирования и их многочисленных модификаций. Первые постановки задач линейного программирования были сформулированыизвестным советским математиком Л.В.Канторовичем, которому за эти работыбыла присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейногопрограммирования получили с изобретением и распространением ЭВМ иформулировкой американским математиком Дж. Данцингом симплекс-метода. В настоящее время линейное программирование является одним из наиболееупотребительных аппаратов математической теории оптимального принятиярешения. Для решения задач линейного программирования разработано сложноепрограмное обеспечение, дающее возможность эффективно и надежно решатьпрактические задачи больших объемов. Эти программы и системы снабженыразвитыми системами подготовки исходных данных, средствами их анализа ипредставления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многихматеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратомлинейного программирования необходимо каждому специалисту в областиматематического программирования. Линейное программирование тесно связано сдругими методами математического программирования (например, нелинейногопрограммирования, где целевая функция нелинейна). Задачи с нелинейной целевой функцией и линейными ограниченияминазывают задачами нелинейного программирования с линейными ограничениями.Оптимизационные задачи такого рода можно классифицировать на основеструктурных особенностей нелинейных целевых функций. Если целевая функция Е- квадратичная функция, то мы имеем дело с задачей квадратичногопрограммирования; если Е – это отношение линейных функций, тосоответствующая задача носит название задачи дробно-линейногопрограммирования, и т.д. Деление оптимизационных задач на эти классыпредставляет значительный интерес, поскольку специфические особенности техили иных задач играют важную роль при разработке методов их решения. Современные методы линейного программирования достаточно надежно решаютзадачи общего вида с несколькими тысячами ограничений и десятками тысячпеременных. Для решения сверхбольших задач используются уже, как правило,специализированные методы. 1. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ Вариант 80. В цехе имеется токарный станок и станок-автомат. Цех выпускает детали1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часоваяпроизводительность станков по каждой из деталей приведена в таблице:| | ||Станки |Детали || | | | || |1 |2 |3 || | | | ||1.Токарный |5 |5 |10 || | | | ||2.Автомат |15 |15 |10 | Таблица 1. Часовая производительность станков Составить программу работы станков, при которой в течение смены (8часов) будет выпускаться максимальное количество комплектов деталей. 2. ПОСТРОЕНИЕ АНАЛИТИЧЕСКОЙ МОДЕЛИ Составим аналитическую модель задачи. Для этого сначала введемпеременные, которые требуется определить: X1 – время, которое работал токарный станок над деталями типа 1 втечение рабочей смены; X2 – время, которое работал токарный станок над деталями типа 2 втечение рабочей смены; X3 – время, которое работал токарный станок над деталями типа 3 втечение рабочей смены; X4 – время, которое работал станок-автомат над деталями типа 1 втечение рабочей смены; X5 – время, которое работал станок-автомат над деталями типа 2 втечение рабочей смены; X6 – время, которое работал станок-автомат над деталями типа 3 втечение рабочей смены. Система ограничений состоит из двух групп. Первая группа устанавливает,что каждый из станков может работать не более 8 часов в смену. Ограничение времени работы токарного станка: X1 + X2 + X3 ( 8; Ограничение времени работы станка-автомата: X4 + X5 + X6 ( 8. Вторая группа ограничений направлена на выполнение требования окомплектации деталей: на каждую деталь 1 должно приходиться по 2 детали 2 и3. Но перед тем, как вводить это ограничение, определим, сколько деталейкаждого типа у нас будет производиться за смену: 5X1 + 15X4 - будет произведено за смену деталей типа 1; 5X2 + 15X5 - будет произведено за смену деталей типа 2; 10X3 + 10X6 - будет произведено за смену деталей типа 3. Теперь введем сами ограничения: 2(5X1 + 15X4) = 5X2 + 15X5; 2(5X1 + 15X4) = 10X3 + 10X6. Очевидно, что все переменные в задаче неотрицательные (объем продукциине может быть отрицательным): X1 , X2 , X3 , X4 , X5 , X6 ? 0. Целевая функция в нашей задаче должна выражать количество комплектовдеталей, выпускаемых за смену, поэтому сложим все выпускаемые детали иподелим на 5 (в комплект, как уже упоминалось, входят 1 деталь типа 1 и по2 детали типа 2 и 3): E= (5X1 + 15X4 + 5X2 + 15X5 + 10X3 + 10X6)/5 ( maxили, если упростить это выражение, то получим: E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 ( max Целевую функцию надо максимизировать. Таким образом, формальная постановка задачи оптимизации имеет следующийвид: X1 + X2 + X3 ( 8; X4 + X5 + X6 ( 8; 2(5X1 + 15X4) = 5X2 + 15X5; 2(5X1 + 15X4) = 10X1 + 10X6; X1 , X2 , X3 , X4 , X5 , X6 ? 0. E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 ( max ОБОСНОВАНИЕ И ОПИСАНИЕ ВЫЧИСЛИТЕЛЬНОЙ ПРОЦЕДУРЫ 1. ПРИВЕДЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К СТАНДАРТНОЙ ФОРМЕ Любая задача линейного программирования приводится к стандартной(канонической) форме основной задачи линейного программирования, котораяформулируется следующим образом: найти неотрицательные значения переменныхX1 , X2 , Xn , удовлетворяющих ограничениям в виде равенств: A11X1 + A12X2 + … + A1nXn = B1; A21X1 + A22X2 + … + A2nXn = B2; …………………………………… Am1X1 + Am2X2 + … + AmnXn = Bm; Xj ? 0, j=1,…,nи обращающих в максимум линейную функцию этих переменных: E = C1X1 + C2X2 + … + CnXn ( max При этом также требуется, чтобы правые части равенств былинеотрицательны, т.е. должны соблюдаться условия: Bj ? 0, j=1,…,n Приведение к стандартной форме необходимо, так как большинство методоврешения задач линейного программирования разработано именно для стандартнойформы. Для приведения к стандартной форме задачи линейного программированияможет потребоваться выполнить следующие действия: - перейти от минимизации целевой функции к ее максимизации; - изменить знаки правых частей ограничений; - перейти от ограничений-неравенств к равенствам; - избавиться от переменных, не имеющих ограничений на знак. Для решения нашей задачи воспользуемся симплекс-методом, так как этотметод предназначен для решения задач линейного программирования любойразмерности. 3.2. ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА Экстремум целевой функции всегда достигается в угловых точках областидопустимых решений. Симплекс-метод, называемый также методомпоследовательного улучшения плана, реализует перебор угловых точек областидопустимых решений в направлении улучшения значения целевой функции.Основная идея этого метода следующая. Прежде всего, находится какое-либодопустимое начальное (опорное) решение, т.е. какая-либо угловая точкаобласти допустимых решений. Процедура метода позволяет ответить на вопрос,является ли это решение оптимальным. Если "да", то задача решена. Если"нет", то выполняется переход к смежной угловой точке области допустимыхрешений, где значение целевой функции улучшается, т.е. к нехудшемудопустимому решению. Если некоторая угловая точка имеет несколько смежных,то вычислительная процедура метода обеспечивает переход к той из них, длякоторой улучшение целевой функции будет наибольшим. Процесс перебораугловых точек области допустимых решений повторяется, пока не будет найденаточка, которой соответствует экстремум целевой функции Е. При построении начального базиса в заданной задаче использовался методискусственного базиса, поэтому найденное решение не является допустимым. Вэтом случае для решения задачи необходимо использовать двухэтапный симплекс-метод. 3.3. ДВУХЭТАПНЫЙ СИМПЛЕКС-МЕТОД Задача с помощью этого метода решается в два этапа: сначалаотыскивается начальное допустимое решение, не содержащее искусственныхпеременных, а затем на основе найденного решения ищется оптимальное решениеисходной задачи. Основные шаги, реализации метода следующие. 1. Задача линейного программирования сводится к стандартной форме. 2. Строится искусственный базис. 3. Составляется искусственная целевая функция: сумма всехискусственных переменных. 4. Реализуется первый этап двухэтапного метода: с помощью обычныхпроцедур симплекс-метода выполняется минимизация искусственной целевойфункции. Если ее минимальное значение равно 0, то соответствующее решениеявляется допустимым решением исходной задачи. Очевидно, что при нулевомзначении искусственной целевой функции все искусственные переменные такженулевые (так как искусственная целевая функция - их сумма, и все онинеотрицательны). Если минимальное значение искусственной целевой функцииоказывается отличным от нуля, это означает, что задача не имеет допустимыхрешений. 5. Реализуется второй этап двухэтапного метода: найденное на шаге 4допустимое решение используется в качестве начального решения исходнойзадачи для поиска ее оптимального решения. 4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ СИМПЛЕКС-ТАБЛИЦ 4.1. ПРИВЕДЕНИЕ ЗАДАЧИ К СТАНДАРТНОЙ ФОРМЕ Для приведения данной задачи к стандартной форме необходимо лишьперейти от ограничений – неравенств к равенствам. Для этого введемдополнительные балансовые неотрицательные переменные. Также для упрощениядальнейших вычислений разделим обе части ограничений на комплектациюдеталей на 5: X1 + X2 + X3 + X7 = 8; X4 + X5 + X6 + X8 = 8; 2X1 – X2 + 6X4 – 3X5 = 0; 2X1 – 2X3 + 6X4 – 2X6 =0; X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8 ? 0. E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 ( maxгде Х7 , Х8 – остаточные переменные. Итак, нашу исходную задачу мы привели к стандартной форме основнойзадачи линейного программирования. 4.2. ОПРЕДЕЛЕНИЕ НАЧАЛЬНОГО ДОПУСТИМОГО РЕШЕНИЯ Для задачи, представленной в стандартной форме, количество переменныхобычно больше, чем количество ограничений. Поэтому для нахожденияначального решения задачи требуется выразить m переменных (т.е. количествопеременных, равное количеству уравнений) через остальные n-m переменных,принять эти n-m переменных равными нулю и, таким образом, найти значения mпеременных (в заданной задаче m=4 и n=8). Переменные, значения которыхпринимаются равными нулю, называются небазисными, а остальные m переменных- базисными. Значения базисных переменных неотрицательны (некоторые из нихмогут оказаться равными нулю). Количество базисных переменных всегда равноколичеству ограничений. Найденное таким образом решение называетсяначальным допустимым базисным решением. Оно соответствует всемограничениям. Начальное решение проще всего найти в случае, когда в каждомограничении есть переменная, которая входит в него с коэффициентом 1 и приэтом отсутствует в других ограничениях. Такие переменные принимаются вкачестве базисных (они образуют начальный базис задачи). Остальные(небазисные) переменные принимаются равными нулю. Таким образом, базисныепеременные принимают значения, равные правым частям ограничений. Итак, для нахождения начального допустимого решения необходимо, чтобыв каждое из уравнений входила переменная с коэффициентом 1 и не входила вдругие уравнения (базисная переменная). В нашем случае мы имеем только 2базисные переменные (X7 и X8) , не хватает еще двух базисных переменных. Ихможно создать с помощью специального способа, который называетсяпостроением искусственного базиса. 4.3. ПОСТРОЕНИЕ ИСКУССТВЕННОГО БАЗИСА Методы искусственного базиса предназначены для построения начальногобазиса (т.е. для получения начального решения) в случаях, когда егопостроение непосредственно на основе стандартной формы невозможно. Прииспользовании искусственного базиса начальное решение оказываетсянедопустимым; от него по определенным алгоритмам выполняется переход кначальному допустимому решению. Для того, чтобы построить искусственный базис, необходимо в каждоеуравнение стандартной формы, не содержащее базисных переменных (т.е.полученное из ограничения-равенства или "не меньше"), добавить по однойискусственной переменной. В нашем случае это: 2X1 – X2 + 6X4 – 3X5 + Х9 = 0; 2X1 – 2X3 + 6X4 – 2X6 + Х10 =0.где Х9 и Х10 – искусственные переменные, не имеющие никакого физическогосмысла, причем Х9 , Х10 ?0. После построения искусственного базиса, придав нулевые значения всемпеременным, кроме базисных, получим начальный базис: Х7 , Х8 , Х9 , Х10 .Всего в базисе имеется четыре переменные и их значения равны правым частямограничений, т.е.: Х7 = 8; Х8 = 8; Х9 = 0; Х10 = 0.Теперь необходимо решить эту задачу, т.е. найти оптимальное допустимоерешение. Для этого воспользуемся двухэтапным симплекс-методом. 4.4. ПЕРВЫЙ ЭТАП ДВУХЭТАПНОГО СИМПЛЕКС-МЕТОДА Итак, на первом этапе двухэтапного метода отыскивается начальноедопустимое решение. Для этого выполним следующие действия: 1. Строим искусственную целевую функцию – сумму всех искусственныхпеременных: W = X9 + X10 ( min 2. Так как целевая функция должна быть выражена только через небазисныепеременные, то выражаем искусственные переменные X9 и X10 через небазисныепеременные, а затем, упростив полученное выражение, переписываемискусственную целевую функцию: X9 = - 2X1 + X2 - 6X4 + 3X5; X10 = - 2X1 + 2X3 - 6X4 + 2X6. W = - 4X1 + X2 + 2X3 – 12X4 + 3X5 + 2X6 ( min 3. Для приведения к стандартной форме направим искусственную целевуюфункцию на максимум, для этого умножим обе ее части на –1: -W = 4X1 - X2 - 2X3 + 12X4 - 3X5 - 2X6 ( max 4. Определяем начальное, недопустимое решение. Базис состоит из четырехпеременных, из них две искусственные, остальные две - остаточные. Базисныепеременные принимают значения, равные ограничениям задачи. Остальныепеременные считаем равными нулю. В этом случае целевая функция Е принимаетзначение 0, искусственная целевая функция –W также принимает значение 0. 5. Составляем исходную симплекс-таблицу:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР ||E |-1 |-1 |-2 |-3 |-3 |-2 |0 |0 |0 |0 |0 ||-W |-4 |1 |2 |-12 |3 |2 |0 |0 |0 |0 |0 ||X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 ||X8 |0 |0 |0 |1 |1 |1 |0 |1 |0 |0 |8 ||X9 |2 |-1 |0 |6 |-3 |0 |0 |0 |1 |0 |0 ||X10 |2 |0 |-2 |6 |0 |-2 |0 |0 |0 |1 |0 | Таблица 2. Симплекс-таблица №1. Итак, в первом столбце таблицы указаны базисные переменные, впоследнем столбце - их значения, а так же значения целевой и искусственнойцелевой функций. В заголовке таблицы перечисляются все используемыепеременные. В строках таблицы указываются коэффициенты ограничений задачи. 6. Реализуем первый этап двухэтапного метода: с помощью процедур симплекс-метода выполняем максимизацию функции -W. При этом переменные, включаемые вбазис, выбираются по W-строке (т.е. на каждом цикле в базис включаетсяпеременная, которой соответствует максимальный по модулю отрицательныйэлемент в W-строке; столбец, соответствующий этой переменной, становитсяведущим). В нашем случае это столбец X4, т. к. коэффициент при этойпеременной в W-строке равен –12. Ведущую строку определяем следующимобразом: рассчитываем так называемые симплексные отношения, т. е. отношениятекущих значений базисных переменных к положительным коэффициентамведущего столбца, соответствующим данным базисным переменным. Затем беремминимальное из этих отношений и по тому, какой строке оно соответствует,определяем ведущую строку. У нас есть три таких отношения: по переменной Х8(8/1=8), Х9 (0/6=0) и Х10 (0/6=0). Получилось два минимальных значения,значит, возьмем любое из них, например по переменной Х9. После находимведущий элемент, он расположен на пересечении ведущей строки и ведущегостолбца (в нашем случае он равен 6). Затем определяем переменные, которыебудем исключать из базиса и включать в него. Переменную, которойсоответствует ведущий столбец, будем включать в базис вместо переменной,которой соответствует ведущая строка. Далее все преобразования выполняем пообычным формулам симплекс-метода или по "правилу прямоугольника".Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР ||E |0 |-1,5 |-2 |0 |-4,5 |-2 |0 |0 |0,5 |0 |0 ||-W |0 |-1 |2 |0 |-3 |2 |0 |0 |2 |0 |0 ||X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 ||X8 |-0,33|0,17 |0 |0 |1,5 |1 |0 |1 |-0,17|0 |8 ||X4 |0,33 |-0,17 |0 |1 |-0,5 |0 |0 |0 |0,17 |0 |0 ||X10 |0 |1 |-2 |0 |3 |-2 |0 |0 |-1 |1 |0 | Таблица 3. Симплекс-таблица №2. Мы получили новое решение (Х7,Х8,Х4,Х10)=(8,8,0,0). Это решениенедопустимо, так как в базисе содержится искусственная переменная Х10.Выполим очередную итерацию. По строке –W для включения в базис выбираемпеременную X5 (т.к. –3 – максимальное по модулю отрицательное число).Столбец X5 становится ведущим. По минимальному симплексному отношению (8/1,5=5,33; 0/3=0) для исключения из базиса выбираем переменную Х10.Ведущий элемент равен 3. После проведенных пересчетов получаем новуюсимплекс-таблицу:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР ||E |0 |0 |-5 |0 |0 |-5 |0 |0 |-1 |1,5 |0 ||-W |0 |0 |0 |0 |0 |0 |0 |0 |1 |1 |0 ||X7 |1 |1 |1 |0 |0 |0 |1 |0 |0 |0 |8 ||X8 |-0,33|-0,33 |1 |0 |0 |2 |0 |1 |0,33 |-0,5 |8 ||X4 |0,33 |0 |-0,33|1 |0 |-0.33|0 |0 |0 |0,17 |0 ||X5 |0 |0,33 |-0,67|0 |1 |-0,67|0 |0 |-0,33|0,33 |0 | Таблица 4. Симплекс-таблица №3. 4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА Итак, как видно из Таблицы 4, все искусственные переменные вышли избазиса, искусственная целевая функция обнулилась – значит, первый этапдвухэтапного симплекс-метода закончен, найдено начальное допустимоерешение: (Х1,X2,X3,X4,X5,X6) = (0,0,0,0,0,0), целевая функция Е=0. Теперьпереходим к реализации второго этапа: вычеркиваем из таблицы строкуискусственной целевой функции и столбцы искусственных переменных; над новойтаблицей выполняем обычные процедуры симплекс-метода, а именно: ведущийстолбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулюотрицательный коэффициент находим по Е-строке целевой функции. Расчет ведемдо тех пор, пока в Е-строке не останется отрицательных коэффициентов:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |БР ||E |0 |0 |-5 |0 |0 |-5 |0 |0 |0 ||X7 |1 |1 |1 |0 |0 |0 |1 |0 |8 ||X8 |-0,33|-0,33 |1 |0 |0 |2 |0 |1 |8 ||X4 |0,33 |0 |-0,33 |1 |0 |-0,33 |0 |0 |0 ||X5 |0 |0,33 |-0,67 |0 |1 |-0,67 |0 |0 |0 | Таблица 5. Симплекс-таблица №4. Наше начальное допустимое решение не является оптимальным, так как в Е-строке содержатся отрицательные коэффициенты. Определим по Е-строке новуюпеременную для включения в базис. Это переменная X3, т.к. –5 – максимальноепо модулю отрицательное число (коэффициент Е-строки при переменной X6 такжеравен –5, поэтому выбрали любую из этих переменных, например X3). СтолбецX3 становится ведущим. По минимальному симплексному отношению ( 8/1=8;8/1=8) для исключения из базиса выбираем переменную Х7 (симплексноеотношение при переменной X8 также равно 8, поэтому выбрали любую из этихпеременных). Ведущий элемент равен 1. После проведенных пересчетов получаемновую симплекс-таблицу:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |БР ||E |5 |5 |0 |0 |0 |-5 |5 |0 |40 ||X3 |1 |1 |1 |0 |0 |0 |1 |0 |8 ||X8 |-1,33|-1,33 |0 |0 |0 |2 |-1 |1 |0 ||X4 |0,67 |0,33 |0 |1 |0 |-0,33 |0,33 |0 |2,67 ||X5 |0,67 |1 |0 |0 |1 |-0,67 |0,67 |0 |5,33 | Таблица 6. Симплекс-таблица №5. Итак, как видно из таблицы, некоторые из искомых переменных , а именноХ3, Х4 и Х5, начали расти, что привело и к росту значения целевой функции –из нулевого значения она приняла значение 40. Это можно объяснить тем, чтоиз точки начального допустимого решения мы перешли к соседней угловой точкеобласти допустимых решений, причем в этой соседней точке рост целевойфункции максимален. Однако в Е-строке есть еще отрицательный коэффициент,поэтому продолжим расчеты. Определим по Е-строке новую переменную для включения в базис. Этопеременная X6, т.к. –5 – максимальное по модулю отрицательное число.Столбец X6 становится ведущим. По минимальному симплексному отношению (0/2=0) для исключения из базиса выбираем переменную Х8. Получаем новуюсимплекс-таблицу:|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |БР ||E |1,67 |1,67 |0 |0 |0 |0 |2,5 |2,5 |40 ||X3 |1 |1 |1 |0 |0 |0 |1 |0 |8 ||X6 |-0,67|-0,67 |0 |0 |0 |1 |-0,5 |0,5 |0 ||X4 |0,44 |0,11 |0 |1 |0 |0 |0,17 |0,17 |2,67 ||X5 |0,22 |0,55 |0 |0 |1 |0 |0,33 |0,33 |5,33 | Таблица 7. Симплекс-таблица №6. Так как все коэффициенты E-строки таблицы 7 положительные, тооптимальное решение найдено. Оптимальный план состоит в том, чтобы токарныйстанок работал над деталями типа 3 8 часов за смену, то есть всю рабочуюсмену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат долженработать за смену 2,67 часа над деталями типа 1 и 5,33 часа над деталямитипа 2 и не должен работать над деталями типа 3. При этом за смену будетвыпускаться максимально возможное количество комплектов деталей, а именно40 комплектов. Ни один из станков не будет простаивать. 5. АНАЛИЗ МОДЕЛИ НА ЧУВСТВИТЕЛЬНОСТЬ В окончательной симплекс-таблице, содержащей оптимальное решение,содержится не только само оптимальное решение, но и другая информация. Наоснове последней симплекс-таблицы решаются задачи анализа начувствительность - определение влияния изменений в исходных данных задачина оптимальное решение. Интерпретация симплекс-таблицы и анализ начувствительность полностью зависят от содержательного смысла конкретнойзадачи. В нашем случае мы имеем дело с задачей о распределения ресурсов, аименно ресурсов времени. 5.1. СТАТУС РЕСУРСОВ По статусу ресурсы делятся на дефицитные и недефицитные. Еслинекоторый ресурс при реализации оптимального плана расходуется полностью,он называется дефицитным, если не полностью - недефицитным. Статус ресурсов определяется по значениям остаточных переменных Х7 иХ8, введенных в исходную систему ограничений для приведения ее кстандартной форме. Эти переменные означают остатки ресурсов при реализацииоптимального плана. Ни одна из остаточных переменных не входит воптимальное решение, т.е. их значения равны нулю. Это означает, чтотокарный станок и станок-автомат использовались все выделенное для ихработы время, т.е. запасы времени работы станков являются дефицитнымиресурсами. Увеличение запасов дефицитных ресурсов позволяет увеличитьзначение целевой функции, а снижение этих запасов приводит к уменьшениюцелевой функции. 5.2. ЦЕННОСТЬ РЕСУРСОВ Ценность ресурса - это величина увеличения значения целевой функции приувеличении запасов данного ресурса на единицу (или соответственно величинауменьшения целевой функции при снижении запаса ресурса). Другое названиеэтой величины - теневая (скрытая) цена. В симплекс-таблице, соответствующейоптимальному решению, теневые цены содержатся в E-строке и представляютсобой коэффициенты при остаточных переменных, соответствующим остаткамресурсов. Таким образом, ценность времени работы токарного станка и станка-автомата соответственно равна по 2,5 комплекта деталей. Другими словами,если запас времени работы токарного станка увеличить (уменьшить) на 1 час,то количество производимых комплектов деталей увеличится (уменьшится) на2,5 единицы, и, аналогично, если увеличить (уменьшить) время работы станка-автомата станка на 1 час, то количество комплектов увеличится (уменьшится)на 2,5 комплекта. 5.3. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ ПРАВЫХ ЧАСТЕЙ ОГРАНИЧЕНИЙ Для анализа решения на чувствительность к изменению запасов времениработы станков (без изменения других исходных данных задачи) используютсякоэффициенты из столбцов остаточных переменных Х7 и Х8 (соответственно длятокарного станка и станка-автомата) в последней симплекс-таблице. Например,если запас времени работы токарного станка изменился на d часов и сталравен 8+d часов, то новое оптимальное решение находится по следующимформулам: Х3 = 8 + 1*d X6 = 0 – 0,5*d X4 = 2,67 + 0,17*d X5 = 5,33 + 0,33*d E = 40 + 2,5*d При составлении этих формул использовали коэффициенты из столбцаостаточной переменной Х7 в последней симплекс-таблице. По содержательномусмыслу эти формулы означают изменение времени работы токарного станка илистанка-автомата над каждой из деталей в сутки при изменении запасадефицитного ресурса. Формула E = 40 + 2,5*d означает изменение количествапроизводимых комплектов деталей в сутки. Например, если время работытокарного станка станет не 8, а 6 часов в сутки, т.е. уменьшится на 2 часа(d=-2), то базисные переменные, а также целевая функция примут следующиезначения: Х3 = 6; Х6 = 1; Х4 = 2,33; Х5 = 4,67; Е = 35. Все остальные переменные равны нулю (они не являются базисными). Как видно, из-за уменьшения запаса времени работы токарного станкауменьшилось время работы этого станка над деталями типа 3, но вместе с темувеличилось время работы станка-автомата над этими же деталями. Так какстанок-автомат стал работать за смену 1 час над деталями третьего типа, тоон уменьшил свое время работы над деталями типа 1 и 2 (ранее он отдавал всесвое время на обработку только этих деталей). И, очевидно, что если времяработы токарного станка уменьшилось, то уменьшится и количество комплектовдеталей, производимых в сутки. Таким образом, для исследования влияния изменения запаса ресурса наоптимальное решение нет необходимости решать задачу заново (с новымограничением). Для нахождения оптимального решения достаточно поокончательной симплекс-таблице исходной задачи составить уравнения иподставить в них величину изменения запаса ресурса (значение d). Изменение запасов ресурсов (т.е. правых частей ограничений) можетпривести к недопустимости оптимального базиса, найденного для исходнойзадачи. Так как на все переменные, используемые в задаче, накладываетсятребование неотрицательности, допустимый диапазон изменения запаса ресурса(т. е. диапазон допустимых значений d) находят из системы неравенств. Такимобразом, допустимый диапазон изменения запаса времени работы токарногостанка, при котором состав переменных в базисе оптимального решения неизменяется, находится из условия: Х3 = 8 + 1*d > 0 Х6 = 0 – 0,5*d > 0 Х4 = 2,67 + 0,17*d > 0 Х5 = 5,33 + 0,33*d > 0 Решив данную систему неравенств, получим, что –8 < d < 0. Такимобразом, базис оптимального решения будет состоять из переменных(Х3,Х6,Х4,Х5), если запас времени работы токарного станка будет находитьсяв диапазоне от 0 до 8 часов. Выход значения d за границы этого диапазонаприведет к недопустимости найденного нами оптимального решения, так какминимум одна из базисных переменных окажется отрицательной, и для того,чтобы найти оптимальное решение, нам придется решать задачу заново. Аналогично выполняется анализ на чувствительность к изменению запасавремени работы станка-автомата. 5.4. АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ К ИЗМЕНЕНИЯМ КОЭФФИЦИЕНТОВ ЦЕЛЕВОЙ ФУНКЦИИ В данной задаче коэффициенты целевой функции имеют сложный физическийсмысл, поэтому анализ на чувствительность к изменению ее коэффициентовпроизводить не будем. ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ЦЕЛОЧИСЛЕННОГО РЕШЕНИЯ Данная задача по своему содержанию является частично целочисленной.Переменные X1 , X2 , X3 , X4 , X5 , X6 ,обозначающие время работыопределенного станка над деталями определенного типа, должны приниматьцелые значения. В то же время, переменные Х7 , Х8, обозначающие времяпростоя соответственно токарного станка и станка-автомата, могут приниматьдробные значения. Для поиска оптимального целочисленного решениявоспользуемся методом Гомори для частично целочисленных задач. 1. МЕТОД ГОМОРИ ДЛЯ ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ Метод Гомори для нахождения целочисленного решения относится к большойгруппе методов, называемых методами отсечений. Эти методы основаны навведении в задачу дополнительных ограничений, позволяющих учесть требованиецелочисленности. Основная идея методов отсечений состоит в том, что наполученное оптимальное нецелочисленное решение накладывается дополнительноеограничение, которое делает это решение недопустимым, но и не отсекает ниодного целочисленного решения от области допустимых решений. Ограничения составляются по финальной симплекс-таблице, в которойполучено оптимальное нецелочисленное решение. При этом на первоначальнуюсистему ограничений накладывается новое ограничение по следующей формуле: L1*W1 + L2*W2 + … +Ln*Wn ? Bi , где Aij, если Aij?0 и Wj можетбыть дробной, (1) (Bi*Aij)/(Bi-1), если Aij<0 и Wj может бытьдробной, (2) Lj = Aij, если Aij(Bi и Wiдолжна быть целой, (3) Bi*(1-Aij)/(1-Bi), если Aij>
  1   2

Добавить документ в свой блог или на сайт

Похожие:

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа По дисциплине: «Теория систем и системный анализ»...

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа по дисциплине: «Исследование социально-экономических и политических процессов»
Целью работы является анализ миграционных процессов в России имеханизма государственного управления ими

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКонтрольная работа по дисциплине тоисатема : «Системный анализ на примере своей организации»

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа по дисциплине «Комплексный анализ производственных систем»

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа на тему: Трастовые операции коммерческих банков по...
Сегодня становатся актуальными детальное изучение роли и места банковских услуг в системе операций коммерческих банков, анализ их...

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа по дисциплине: «Общая социология» на тему: «Анализ суицида в России»

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа по дисциплине: менеджмент Тема: «Формирование и анализ организационных структур»

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconИсследование операций сравнительно молодая наука, возникла в Англии...
Системный анализ занимается исследованием сложных систем различной природы : технических, экономических, экологических

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconКурсовая работа по дисциплине «Инвестиции» Тема: «Анализ инвестиционных...

Курсовая работа по дисциплине «Системный анализ и исследование операций» iconСовременный системный анализ является прикладной наукой, нацеленной...
Изучение системного анализа базируется на знаниях, получаемых при изучении таких курсов, как экономическая теория, высшая математика,...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<