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

Белорусский государственный университет информатики и радиоэлектроники Факультет информационных технологий и управления Кафедра информационных технологий автоматизированных систем К защите допускаю Н.В. Батин 2001г. КУРСОВАЯ РАБОТА по дисциплине Системный анализ и исследование операций на тему Решение оптимизационной задачи линейного программирования Выполнил студент гр. 920603 Журавкин А.В. Руководитель работы Батин Н.В. Минск, 2001 СОДЕРЖАНИЕ ВВЕДЕНИЕ 1. Постановка задачи оптимизации.2. Построение аналитической модели.3. Обоснование и описание вычислительной процедуры 1. Приведение задачи линейного программирования к стандартной форме 2. Основная идея симлекс-метода 3. Двухэтапный симплекс-метод12 4. Решение задачи оптимизации на основе симплекс-таблиц1. Приведение задачи к стандартной форме 2. Определение начального допустимого решения3. Построение искусственного базиса 4. Первый этап двухэтапного симплекс-метода.5. Второй этап двухэтапного метода.5. Анализ модели на чувствительность 1. Статус ресурсов.2. Ценность ресурсов3. Анализ на чувствительность к изменениям правых частей ограничений 4. Анализ на чувствительность к изменениям коэффициентов целевой функции 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.

Построение аналитической модели

. Теперь введем сами ограничения 25X1 15X4 5X2 15X5 25X1 15X4 10X3 10X6. Ограничение времени работы токарного станка X1 X2 X3 8 Ограничение вре... Но перед тем, как вводить это ограничение, определим, сколько деталей ... Построение аналитической модели.

Обоснование и описание вычислительной процедуры

Обоснование и описание вычислительной процедуры 3.1. Приведение задачи линейного программирования к стандартной форме Любая задача линейного программирования приводится к стандартной канонической форме основной задачи линейного программирования, которая формулируется следующим образом найти неотрицательные значения переменных X1 , X2 , Xn, удовлетворяющих ограничениям в виде равенств A11X1 A12X2 A1nXn B1 A21X1 A22X2 A2nXn B2 Am1X1 Am2X2 AmnXn Bm Xj 0, j1 n и обращающих в максимум линейную функцию этих переменных E C1X1 C2X2 CnXn max При этом также требуется, чтобы правые части равенств были неотрицательны, т.е. должны соблюдаться условия Bj 0, j1 n Приведение к стандартной форме необходимо, так как большинство методов решения задач линейного программирования разработано именно для стандартной формы.

Для приведения к стандартной форме задачи линейного программирования может потребоваться выполнить следующие действия - перейти от минимизации целевой функции к ее максимизации - изменить знаки правых частей ограничений - перейти от ограничений-неравенств к равенствам - избавиться от переменных, не имеющих ограничений на знак. Для решения нашей задачи воспользуемся симплекс-методом, так как этот метод предназначен для решения задач линейного программирования любой размерности. 3.2. ОСНОВНАЯ ИДЕЯ СИМПЛЕКС-МЕТОДА Экстремум целевой функции всегда достигается в угловых точках области допустимых решений.

Симплекс-метод, называемый также методом последовательного улучшения плана, реализует перебор угловых точек области допустимых решений в направлении улучшения значения целевой функции. Основная идея этого метода следующая.

Прежде всего, находится какое-либо допустимое начальное опорное решение, т.е. какая-либо угловая точка области допустимых решений.

Процедура метода позволяет ответить на вопрос, является ли это решение оптимальным.

Если да, то задача решена.

Если нет, то выполняется переход к смежной угловой точке области допустимых решений, где значение целевой функции улучшается, т.е. к нехудшему допустимому решению. Если некоторая угловая точка имеет несколько смежных, то вычислительная процедура метода обеспечивает переход к той из них, для которой улучшение целевой функции будет наибольшим.

Процесс перебора угловых точек области допустимых решений повторяется, пока не будет найдена точка, которой соответствует экстремум целевой функции Е. При построении начального базиса в заданной задаче использовался метод искусственного базиса, поэтому найденное решение не является допустимым. В этом случае для решения задачи необходимо использовать двухэтапный симплекс-метод. 3.3. ДВУХЭТАПНЫЙ СИМПЛЕКС-МЕТОД Задача с помощью этого метода решается в два этапа сначала отыскивается начальное допустимое решение, не содержащее искусственных переменных, а затем на основе найденного решения ищется оптимальное решение исходной задачи.

Основные шаги, реализации метода следующие. 1. Задача линейного программирования сводится к стандартной форме. 2. Строится искусственный базис. 3. Составляется искусственная целевая функция сумма всех искусственных переменных. 4. Реализуется первый этап двухэтапного метода с помощью обычных процедур симплекс-метода выполняется минимизация искусственной целевой функции.

Если ее минимальное значение равно 0, то соответствующее решение является допустимым решением исходной задачи. Очевидно, что при нулевом значении искусственной целевой функции все искусственные переменные также нулевые так как искусственная целевая функция - их сумма, и все они неотрицательны. Если минимальное значение искусственной целевой функции оказывается отличным от нуля, это означает, что задача не имеет допустимых решений. 5. Реализуется Второй этап двухэтапного метода найденное на шаге 4 допустимое решение используется в качестве начального решения исходной задачи для поиска ее оптимального решения. 4. РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ НА ОСНОВЕ СИМПЛЕКС- ТАБЛИЦ 4.1.

Приведение задачи к стандартной форме

Для приведения данной задачи к стандартной форме необходимо лишь перей... Приведение задачи к стандартной форме. E X1 X2 2X3 3X4 3X5 2X6 max где Х7 , Х8 остаточные переменные. Итак, н... . Также для упрощения дальнейших вычислений разделим обе части ограничен...

Определение начального допустимого решения

Определение начального допустимого решения. Для задачи, представленной в стандартной форме, количество переменных ... Такие переменные принимаются в качестве базисных они образуют начальны... Остальные небазисные переменные принимаются равными нулю. 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. Составляем исходную симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE-1-1-2-3-3-20- W-412-12320X711100010008X800011101008X92 -106-3000100X1020-260-200010Таблица 2. Симплекс-таблица 1. Итак, в первом столбце таблицы указаны базисные переменные, в последнем столбце - их значения, а так же значения целевой и искусственной целевой функций.

В заголовке таблицы перечисляются все используемые переменные. В строках таблицы указываются коэффициенты ограничений задачи. 6. Реализуем первый этап двухэтапного метода с помощью процедур симплекс- метода выполняем максимизацию функции -W. При этом переменные, включаемые в базис, выбираются по W-строке т.е. на каждом цикле в базис включается переменная, которой соответствует максимальный по модулю отрицательный элемент в W-строке столбец, соответствующий этой переменной, становится ведущим.

В нашем случае это столбец X4, т. к. коэффициент при этой переменной в W-строке равен 12. Ведущую строку определяем следующим образом рассчитываем так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным коэффициентам ведущего столбца, соответствующим данным базисным переменным.

Затем берем минимальное из этих отношений и по тому, какой строке оно соответствует, определяем ведущую строку. У нас есть три таких отношения по переменной Х8 818, Х9 060 и Х10 060. Получилось два минимальных значения, значит, возьмем любое из них, например по переменной Х9. После находим ведущий элемент, он расположен на пересечении ведущей строки и ведущего столбца в нашем случае он равен 6. Затем определяем переменные, которые будем исключать из базиса и включать в него. Переменную, которой соответствует ведущий столбец, будем включать в базис вместо переменной, которой соответствует ведущая строка.

Далее все преобразования выполняем по обычным формулам симплекс-метода или по правилу прямоугольника. Преобразованиям подвергается вся симплекс-таблица, включая E-строку, W-строку и столбец решений. Получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE0-1,5-20-4,5-2 000,500-W0-120-3200200X711100010008X8-0, 330,17001,5101-0,1708X40,33-0,1701-0,500 00,1700X1001-203-200-110Таблица 3. Симплекс-таблица 2. Мы получили новое решение Х7,Х8,Х4,Х108,8,0,0. Это решение недопустимо, так как в базисе содержится искусственная переменная Х10. Выполим очередную итерацию.

По строке W для включения в базис выбираем переменную X5 т.к. 3 максимальное по модулю отрицательное число. Столбец X5 становится ведущим. По минимальному симплексному отношению 81,55,33 030 для исключения из базиса выбираем переменную Х10. Ведущий элемент равен 3. После проведенных пересчетов получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8X9X10БРE00-500-500-11, 50-W0110X711100010008X8-0,33-0,331002010 ,33-0,58X40,330-0,3310-0.330000,170X500, 33-0,6701-0,6700-0,330,330Таблица 4. Симплекс-таблица 3. 4.5. ВТОРОЙ ЭТАП ДВУХЭТАПНОГО СИМЛЕКС-МЕТОДА Итак, как видно из Таблицы 4, все искусственные переменные вышли из базиса, искусственная целевая функция обнулилась значит, первый этап двухэтапного симплекс-метода закончен, найдено начальное допустимое решение Х1,X2,X3,X4,X5,X6 0,0,0,0,0,0, целевая функция Е0. Теперь переходим к реализации второго этапа вычеркиваем из таблицы строку искусственной целевой функции и столбцы искусственных переменных над новой таблицей выполняем обычные процедуры симплекс-метода, а именно ведущий столбец определяется также, как и для первого этапа двухэтапного симплекс-метода, единственное различие состоит в том, что максимальный по модулю отрицательный коэффициент находим по Е-строке целевой функции.

Расчет ведем до тех пор, пока в Е-строке не останется отрицательных коэффициентов БПX1X2X3X4X5X6X7X8БРE00-500-5000X7111000 108X8-0,33-0,331002018X40,330-0,3310-0,3 3000X500,33-0,6701-0,67000Таблица 5. Симплекс-таблица 4. Наше начальное допустимое решение не является оптимальным, так как в Е-строке содержатся отрицательные коэффициенты.

Определим по Е-строке новую переменную для включения в базис.

Это переменная X3, т.к. 5 максимальное по модулю отрицательное число коэффициент Е-строки при переменной X6 также равен 5, поэтому выбрали любую из этих переменных, например X3. Столбец X3 становится ведущим.

По минимальному симплексному отношению 818 818 для исключения из базиса выбираем переменную Х7 симплексное отношение при переменной X8 также равно 8, поэтому выбрали любую из этих переменных. Ведущий элемент равен 1. После проведенных пересчетов получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8БРE55000-55040X3111000 108X8-1,33-1,330002-110X40,670,33010-0,3 30,3302,67X50,671001-0,670,6705,33Таблиц а 6. Симплекс-таблица 5. Итак, как видно из таблицы, некоторые из искомых переменных, а именно Х3, Х4 и Х5, начали расти, что привело и к росту значения целевой функции из нулевого значения она приняла значение 40. Это можно объяснить тем, что из точки начального допустимого решения мы перешли к соседней угловой точке области допустимых решений, причем в этой соседней точке рост целевой функции максимален.

Однако в Е-строке есть еще отрицательный коэффициент, поэтому продолжим расчеты. Определим по Е-строке новую переменную для включения в базис.

Это переменная X6, т.к. 5 максимальное по модулю отрицательное число. Столбец X6 становится ведущим. По минимальному симплексному отношению 020 для исключения из базиса выбираем переменную Х8. Получаем новую симплекс-таблицу БПX1X2X3X4X5X6X7X8БРE1,671,6700002,52,54 0X3111000108X6-0,67-0,670001-0,50,50X40, 440,1101000,170,172,67X50,220,5500100,33 0,335,33Таблица 7. Симплекс-таблица 6. Так как все коэффициенты E-строки таблицы 7 положительные, то оптимальное решение найдено.

Оптимальный план состоит в том, чтобы токарный станок работал над деталями типа 3 8 часов за смену, то есть всю рабочую смену, и не работал над деталями типа 1 и 2 вообще. Станок-автомат должен работать за смену 2,67 часа над деталями типа 1 и 5,33 часа над деталями типа 2 и не должен работать над деталями типа 3. При этом за смену будет выпускаться максимально возможное количество комплектов деталей, а именно 40 комплектов.

Ни один из станков не будет простаивать. 5.

Анализ модели на чувствительность

В окончательной симплекс-таблице, содержащей оптимальное решение, соде... Интерпретация симплекс-таблицы и анализ на чувствительность полностью ... СТАТУС РЕСУРСОВ По статусу ресурсы делятся на дефицитные и недефицитны... Это означает, что токарный станок и станок-автомат использовались все ... Увеличение запасов дефицитных ресурсов позволяет увеличить значение це...

Ценность ресурсов

. Ценность ресурсов. 5.3. Таким образом, ценность времени работы токарного станка и станка-автом... Ценность ресурса - это величина увеличения значения целевой функции пр...

Анализ на чувствительность к изменениям правых частей ограничений

Для анализа решения на чувствительность к изменению запасов времени ра... И, очевидно, что если время работы токарного станка уменьшилось, то ум... 5.4. Изменение запасов ресурсов т.е. .

Анализ на чувствительность к изменениям коэффициентов целевой функции

Анализ на чувствительность к изменениям коэффициентов целевой функции В данной задаче коэффициенты целевой функции имеют сложный физический смысл, поэтому анализ на чувствительность к изменению ее коэффициентов производить не будем. 6.

Определение оптимального целочисленного решения

Определение оптимального целочисленного решения Данная задача по своему содержанию является частично целочисленной.

Переменные X1 , X2 , X3 , X4 , X5 , X6 ,обозначающие время работы определенного станка над деталями определенного типа, должны принимать целые значения. В то же время, переменные Х7 , Х8, обозначающие время простоя соответственно токарного станка и станка-автомата, могут принимать дробные значения. Для поиска оптимального целочисленного решения воспользуемся методом Гомори для частично целочисленных задач. 6.1.

Метод Гомори для частично целочисленных задач

При этом на первоначальную систему ограничений накладывается новое огр... В нашем случае переменная, имеющая максимальную дробную часть это Х4 2... Все значения базисных переменных стали неотрицательными, это означает ... Решение все еще не целочисленное, поэтому переходим к следующей итерац... В5Х5 4,89 0,89.

ЗАКЛЮЧЕНИЕ

ЗАКЛЮЧЕНИЕ После проведенных вычислений, решив задачу оптимизации, мы получили следующие результаты оптимальный план работы станков состоит в том, чтобы токарный станок работал 1 час над деталями типа 1, 2 часа над деталями типа 2 и 5 часов над деталями типа 3 за смену станок-автомат должен работать 2 часа над деталями типа 1 , 4 часа над деталями типа 2 и 2 часа над деталями типа 3 за смену.

При этом количество комплектов деталей, выпускаемых цехом, будет максимально и равно 35. В результате проведенного анализа на чувствительность к изменению запаса времени работы токарного станка получили, что если запас времени работы этого станка будет находиться в пределах от 0 до 8 часов, то базис оптимального решения останется неизменным, т.е. будет состоять из переменных Х3,Х6,Х4,Х5.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 1. Смородинский С.С Батин Н.В. Методы и алгоритмы для решения оптимизационных задач линейного программирования.

Ч.1. Мн. БГУИР, 1995. 2. Смородинский С.С Батин Н. В. Методы и алгоритмы для решения оптимизационных задач линейного программирования.

Ч.2. Мн. БГУИР, 1996. 3. Смородинский С.С Батин Н.В. Анализ и оптимизация систем на основе аналитических моделей Мн. БГУИР, 1997. 4. Дегтярев Ю.И. Исследование операций М. Высшая школа, 1986.

УСЛОВНЫЕ СОКРАЩЕНИЯ

УСЛОВНЫЕ СОКРАЩЕНИЯ БР базисное решение БП базисная переменная Условие задачи.

ПРИЛОЖЕНИЕ

ПРИЛОЖЕНИЕ .

X1 X2 X3 X4 X5 X6 Вид огр. Значение -1.00 -1.00 -2.00 -3.00 -3.00 -2.00 E 2.00 -1.00 0.00 6.00 -3.00 0.00 0.00 2.00 0.00 -2.00 6.00 0.00 -2.00 0.00 1.00 1.00 1.00 0.00 0.00 0.00 8.00 0.00 0.00 0.00 1.00 1.00 1.00 8.00 Вывод промежуточных результатов оптимизации.

N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Баз. Реш. 1 E -1.00 -1.00 -2.00 -3.00 -3.00 -2.00 0.00 0.00 0.00 0.00 0.00 -W -4.00 1.00 2.00 -12.00 3.00 2.00 0.00 0.00 0.00 0.00 0.00 X9 2.00 -1.00 0.00 6.00 -3.00 0.00 0.00 0.00 1.00 0.00 0.00 X10 2.00 0.00 -2.00 6.00 0.00 -2.00 0.00 0.00 0.00 1.00 0.00 X7 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 8.00 X8 0.00 0.00 0.00 1.00 1.00 1.00 0.00 1.00 0.00 0.00 8.00 Ведущий элемент находится в 4 столбце и 1 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Баз. Реш. 2 E 0.00 -1.50 -2.00 0.00 -4.50 -2.00 0.00 0.00 0.50 0.00 0.00 -W 0.00 -1.00 2.00 0.00 -3.00 2.00 0.00 0.00 2.00 0.00 0.00 X4 0.33 -0.17 0.00 1.00 -0.50 0.00 0.00 0.00 0.17 0.00 0.00 X10 0.00 1.00 -2.00 0.00 3.00 -2.00 0.00 0.00 -1.00 1.00 0.00 X7 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 8.00 X8 -0.33 0.17 0.00 0.00 1.50 1.00 0.00 1.00 -0.17 0.00 8.00 Ведущий элемент находится в 5 столбце и 2 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Баз. Реш. 3 E 0.00 0.00 -5.00 0.00 0.00 -5.00 0.00 0.00 -1.00 1.50 0.00 -W 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 1.00 1.00 0.00 X4 0.33 0.00 -0.33 1.00 0.00 -0.33 0.00 0.00 0.00 0.17 0.00 X5 0.00 0.33 -0.67 0.00 1.00 -0.67 0.00 0.00 -0.33 0.33 0.00 X7 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 0.00 0.00 8.00 X8 -0.33 -0.33 1.00 0.00 0.00 2.00 0.00 1.00 0.33 -0.50 8.00 Вывод промежуточных результатов оптимизации.

N БП X1 X2 X3 X4 X5 X6 X7 X8 Баз. Реш. 3 E 0.00 0.00 -5.00 0.00 0.00 -5.00 0.00 0.00 0.00 X4 0.33 0.00 -0.33 1.00 0.00 -0.33 0.00 0.00 0.00 X5 0.00 0.33 -0.67 0.00 1.00 -0.67 0.00 0.00 0.00 X7 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 8.00 X8 -0.33 -0.33 1.00 0.00 0.00 2.00 0.00 1.00 8.00 Ведущий элемент находится в 3 столбце и 3 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 Баз. Реш. 4 E 5.00 5.00 0.00 0.00 0.00 -5.00 5.00 0.00 40.00 X4 0.67 0.33 0.00 1.00 0.00 -0.33 0.33 0.00 2.67 X5 0.67 1.00 0.00 0.00 1.00 -0.67 0.67 0.00 5.33 X3 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 8.00 X8 -1.33 -1.33 0.00 0.00 0.00 2.00 -1.00 1.00 0.00 Ведущий элемент находится в 6 столбце и 4 строке. Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 Баз. Реш. 5 E 1.67 1.67 0.00 0.00 0.00 0.00 2.50 2.50 40.00 X4 0.44 0.11 0.00 1.00 0.00 0.00 0.17 0.17 2.67 X5 0.22 0.56 0.00 0.00 1.00 0.00 0.33 0.33 5.33 X3 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 8.00 X6 -0.67 -0.67 0.00 0.00 0.00 1.00 -0.50 0.50 0.00 Результаты оптимизации.

Базис Значение X4 2.67 X5 5.33 X3 8.00 X6 0.00 Максимум функции равен 40.00 Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 Баз. Реш. 1 E 1.67 1.67 0.00 0.00 0.00 0.00 2.50 2.50 0.00 40.00 X4 0.44 0.11 0.00 1.00 0.00 0.00 0.17 0.17 0.00 2.67 X5 0.22 0.56 0.00 0.00 1.00 0.00 0.33 0.33 0.00 5.33 X3 1.00 1.00 1.00 0.00 0.00 0.00 1.00 0.00 0.00 8.00 X6 -0.67 -0.67 0.00 0.00 0.00 1.00 -0.50 0.50 0.00 0.00 X9 -0.44 -0.11 0.00 0.00 0.00 0.00 -0.17 -0.17 1.00 -0.67 Ведущий элемент находится в 1 столбце и 5 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 Баз. Реш. 2 E -0.00 1.25 0.00 0.00 0.00 0.00 1.88 1.88 3.75 37.50 X4 -0.00 -0.00 0.00 1.00 0.00 0.00 -0.00 -0.00 1.00 2.00 X5 -0.00 0.50 0.00 0.00 1.00 0.00 0.25 0.25 0.50 5.00 X3 -0.00 0.75 1.00 0.00 0.00 0.00 0.62 -0.38 2.25 6.50 X6 -0.00 -0.50 -0.00 -0.00 -0.00 1.00 -0.25 0.75 -1.50 1.00 X1 1.00 0.25 -0.00 -0.00 -0.00 -0.00 0.38 0.38 -2.25 1.50 Результаты оптимизации.

Базис Значение X4 2.00 X5 5.00 X3 6.50 X6 1.00 X1 1.50 Максимум функции равен 37.50 Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Баз. Реш. 2 E -0.00 1.25 0.00 0.00 0.00 0.00 1.88 1.88 3.75 0.00 37.50 X4 -0.00 -0.00 0.00 1.00 0.00 0.00 -0.00 -0.00 1.00 0.00 2.00 X5 -0.00 0.50 0.00 0.00 1.00 0.00 0.25 0.25 0.50 0.00 5.00 X3 -0.00 0.75 1.00 0.00 0.00 0.00 0.62 -0.38 2.25 0.00 6.50 X6 -0.00 -0.50 -0.00 -0.00 -0.00 1.00 -0.25 0.75 -1.50 0.00 1.00 X1 1.00 0.25 -0.00 -0.00 -0.00 -0.00 0.38 0.38 -2.25 0.00 1.50 X10 0.00 -0.25 0.00 0.00 0.00 0.00 -0.38 -0.38 -2.25 1.00 -0.50 Ведущий элемент находится в 9 столбце и 6 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 Баз. Реш. 3 E -0.00 0.83 0.00 0.00 0.00 0.00 1.25 1.25 -0.00 1.67 36.67 X4 -0.00 -0.11 0.00 1.00 0.00 0.00 -0.17 -0.17 -0.00 0.44 1.78 X5 -0.00 0.44 0.00 0.00 1.00 0.00 0.17 0.17 -0.00 0.22 4.89 X3 -0.00 0.50 1.00 0.00 0.00 0.00 0.25 -0.75 -0.00 1.00 6.00 X6 -0.00 -0.33 -0.00 -0.00 -0.00 1.00 -0.00 1.00 -0.00 -0.67 1.33 X1 1.00 0.50 -0.00 -0.00 -0.00 -0.00 0.75 0.75 -0.00 -1.00 2.00 X9 -0.00 0.11 -0.00 -0.00 -0.00 -0.00 0.17 0.17 1.00 -0.44 0.22 Результаты оптимизации.

Базис Значение X4 1.78 X5 4.89 X3 6.00 X6 1.33 X1 2.00 X9 0.22 Максимум функции равен 36.67 Вывод промежуточных результатов оптимизации.

N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 Баз. Реш. 3 E -0.00 0.83 0.00 0.00 0.00 0.00 1.25 1.25 -0.00 1.67 0.00 36.67 X4 -0.00 -0.11 0.00 1.00 0.00 0.00 -0.17 -0.17 -0.00 0.44 0.00 1.78 X5 -0.00 0.44 0.00 0.00 1.00 0.00 0.17 0.17 -0.00 0.22 0.00 4.89 X3 -0.00 0.50 1.00 0.00 0.00 0.00 0.25 -0.75 -0.00 1.00 0.00 6.00 X6 -0.00 -0.33 -0.00 -0.00 -0.00 1.00 -0.00 1.00 -0.00 -0.67 0.00 1.33 X1 1.00 0.50 -0.00 -0.00 -0.00 -0.00 0.75 0.75 -0.00 -1.00 0.00 2.00 X9 -0.00 0.11 -0.00 -0.00 -0.00 -0.00 0.17 0.17 1.00 -0.44 0.00 0.22 X11 0.00 -0.44 0.00 0.00 0.00 0.00 -0.17 -0.17 0.00 -0.22 1.00 -0.89 Ведущий элемент находится в 2 столбце и 7 строке.

Вывод промежуточных результатов оптимизации. N БП X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 Баз. Реш. 4 E -0.00 -0.00 0.00 0.00 0.00 0.00 0.94 0.94 -0.00 1.25 1.88 35.00 X4 -0.00 -0.00 -0.00 1.00 -0.00 -0.00 -0.12 -0.12 -0.00 0.50 -0.25 2.00 X5 -0.00 -0.00 0.00 0.00 1.00 0.00 -0.00 -0.00 -0.00 -0.00 1.00 4.00 X3 -0.00 -0.00 1.00 0.00 0.00 0.00 0.06 -0.94 -0.00 0.75 1.13 5.00 X6 -0.00 -0.00 -0.00 -0.00 -0.00 1.00 0.12 1.12 -0.00 -0.50 -0.75 2.00 X1 1.00 -0.00 -0.00 -0.00 -0.00 -0.00 0.56 0.56 -0.00 -1.25 1.12 1.00 X9 -0.00 -0.00 -0.00 -0.00 -0.00 -0.00 0.12 0.12 1.00 -0.50 0.25 0.00 X2 -0.00 1.00 -0.00 -0.00 -0.00 -0.00 0.38 0.38 -0.00 0.50 -2.25 2.00 Результаты оптимизации.

Базис Значение X4 2.00 X5 4.00 X3 5.00 X6 2.00 X1 1.00 X9 0.00 X2 2.00 Максимум функции равен 35.00.