Федеральное агентство по образованию
Санкт-Петербургский Государственный Политехнический Университет
Факультет технической кибернетики
Кафедра «Системный анализ и управление»
Работа допущена к защите
Заведующий кафедрой
____________ В.Н. Козлов
«___» __________ 2010 г.
ДИПЛОМНАЯ РАБОТА
Тема: Решения задачи планирования производства симплекс методом.
Специальность:230201 – Информационные системы и технологии
Выполнил студент гр. 6082/2Дегтярёв И.В.
Руководитель, к.т.н.,доцент Болотин И.В.
Санкт-Петербург
2010
Санкт-Петербургский государственный политехнический университет
Факультет технической кибернетики
Кафедра «Системный анализ и управление»
УТВЕРЖДАЮ
«___» ____________2010 г.
Зав. кафедрой _______________
ЗАДАНИЕ
по дипломному проектированию
студенту Дегтярёву И.В.
группа 6082/2
1. Тема проекта (работы)______________________________________
_________________________________________________________________________________________________________________________________
2. Срок сдачи студентомзаконченного проекта (работы)___________________________________________________________
3. Исходные данные кпроекту (работе)___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
4. Содержаниерасчетно-пояснительной записки (перечень подлежащих разработке вопросов)_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
5. Перечень графическогоматериала (с точным указанием обязательных чертежей)____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
6. Консультанты по проекту(с указанием относящихся к ним разделов проекта, работы)_______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
7. Дата выдачи задания________________________________________
Руководитель_________________________________________________
Задание принял кисполнению___________________________________
Реферат
Дипломная работа представленана 94 страницах машинописного текста, содержит 15 рисунков, 9 таблиц, 11наименований использованных источников.
В данной дипломной работерешается задача планирования производства, являющаяся общей задачей линейногопрограммирования (ЛП). Для решения поставленной задачи использовалсясимплекс-метод, т.к. он является наиболее известным, достаточно эффективным ишироко применяемым на практике для решения прикладных задач линейногопрограммирования. Во вспомогательных целях была использована надстройка MSExcel «Поиск решения».
Так же в среде объектно-ориентированногопрограммирования С++ была реализована программа для решения задач линейногопрограммирования симплекс-методом (в частности поставленной задачи планированияпроизводства).
Перечень используемыхсокращений
ЛП – Линейноепрограммирование;
ЦЛП – Целочисленноелинейное программирование;
ЗЛП – Задача линейногопрограммирования;
ОДР – Область допустимыхрешений;
MS Excel – MicrosoftExcel;
ОС – Операционная система
Содержание
Введение
1. Обзорнаучно-технической литературы
1.1 Историяразвития экономико-математического планирования
1.2Необходимость решения задач линейногопрограммирования
1.3 Линейноепрограммирование
1.4 Математическая формулировка задачи линейногопрограммирования
1.5Постановка задачи целочисленного программирования
2. Обзоросновных алгоритмов решения задач ЛП
2.1Целочисленное линейное программирование — метод отсечений Гомори
2.1.1Отсечения
2.1.2Описание алгоритма
2.2Целочисленное линейное программирование — метод ветвей и границ
2.2.1 Общееописание
2.2.2Применение
2.2.3Алгоритм решения
2.3 Симплексметод
2.3.1Описание
2.3.2Алгоритм симплекс-метода
2.3.2.1Усиленная постановка задачи
2.3.2.2Алгоритм
2.4 Решениезадач оптимизации при помощи средства «Поиск решения» вMicrosoft Excel
2.4.1Описание
2.4.2Процедура поиска решения
2.4.3Параметры средства «Поиск решения»
3. Задачапланирования производства
3.1Постановка задачи планирования производства в общем случае
3.2 Математическое описание поставленной задачи планирования симплексметодом
3.3 Решениепоставленной задачи планирования производства
3.3.4Проверка признака допустимости и оптимальности базиса
3.3.5Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса
3.3.6 Пересчет симплекс-таблицы
3.4Результат решения задачи планирования производства
4. Программадля решения задач ЛП симплекс методом
4.1 Описание
4.2Графическое представление программы
4.3 Работа спрограммой
4.4 Схемапрограммы
Заключение
Списоклитературы
Введение
В процессе хозяйственнойдеятельности сырьевая база предприятия занимает одно из центральных мест,поэтому вопрос об оптимизации сырья на предприятии при планировании выпускаемойпродукции актуален в настоящее время.
Актуальность данной темытакже заключается в том, что в процессе производственной деятельности всепредприятия сталкиваются с проблемой нехватки сырья, а также с тем, что выпускаемаяпродукция должна быть адекватна с экономической точки зрения, другими словами,чтобы её можно было выгодно продать, и чтобы она соответствовала запросампокупателя.
Учитывая всевозрастающуюограниченность ресурсов, очень важно добиваться их максимально эффективногоиспользования. План должен быть разработан настолько умело, чтобы использованиеограниченных ресурсов было оптимальным.
Существует много причин,заставляющих промышленные предприятия заниматься оптимизацией структуры сырья:
улучшение финансовыхпоказателей;
повышение уровняпроизводства;
наращивание объемовпроизводства.
Планирование выпускапродукции также имеет огромное значение для предприятия, оно тесновзаимосвязано с сырьевой базой предприятия.
Сущность планированияпродукции состоит в обосновании целей и способов их достижения на основевыявления комплекса задач и работ, а также определения эффективных методов испособов, ресурсов всех видов, необходимых для выполнения этих задач иустановления их взаимодействия.
Оптимизация структуры сырьяпри планировании выпуска продукции является существенным источником резервовувеличения суммы прибыли. Логично предположить, что предприятию выгодноувеличивать доли тех изделий, которые приносят максимальную прибыль. Но всегдаследует помнить о ряде ограничений, не позволяющих отказаться от менеерентабельной продукции:
1) Потенциальный спрос напродукцию достаточно динамичен и дифференцирован во времени и пространстве. Теизделия и торговые марки, которые востребованы в данный момент времени, могут потерятьсвою потребительскую привлекательность через некоторые промежутки времени;
2) Основныепроизводственные фонды нуждаются в постоянной эксплуатации, наладке иобслуживании. Простои оборудования – это всегда неблагоприятный фактор дляпроизводства.
Планом выпуска продукцииопределяются:
Количественные показателипроизводства;
Объем реализации,ожидаемый в планируемом периоде. Этот показатель определяется на основе объемавыпуска продукции и ожидаемой средней цены реализации 1 учетной единицыпродукции. Ожидаемая средняя цена реализации определяется на основеретроспективного анализа данных за предыдущие несколько лет с учетом ожидаемыхи текущих темпов инфляции.
Для каждого периода,охватываемого планом, необходимо определить две переменные: объём производствав данный период; количество ресурсов, используемых в данный период.
План выпуска продукцииотражает номенклатуру и ассортимент производства продукции в соответствии спланом реализации, обязательствами предприятия и экономическими условиями.
Планирование выпускаемойпродукции включает решение ряда задач. Прежде всего, планируется номенклатура,ассортимент и объем выпуска продукции. Номенклатура производства представляетсобой перечень изделий (готовых изделий, полуфабрикатов и т. п.), подлежащих изготовлениюна предприятии в плановом периоде. Ассортимент продукции характеризуетсоотношение удельных весов отдельных видов изделий в общем, выпуске продукции.Номенклатура, ассортимент и объем изготовляемой предприятием продукцииустанавливаются на основе централизованного задания по поставкам важнейшихвидов продукции и портфеля заказов предприятия с учетом его специализации. Приэтом учитываются и договоры по кооперированным поставкам, заключенныепредприятием.
Целесообразносовершенствовать структуру выпуска только той продукции, удельный вес которой вобщем объеме выпуска достаточно высок.
Необходимым условиемувеличения количества производства определенных изделий являетсяуниверсальность оборудования для их производства.
План выпуска продукцииможет повлиять на величину целого ряда издержек, в том числе: издержки храненияготовой продукции; издержки ведения портфеля отложенных заказав; издержки,связанные с внеурочной работой или простоем работников; издержки, связанные спередачей части работ субподрядчикам; издержки, связанные с наймом иувольнением работников.
Задача оптимизацииструктуры сырья при планировании выпуска продукции должна решаться на каждомпромышленном предприятии, которое заинтересовано в максимизации прибыли отпродажи выпускаемой продукции. Такая задача является задачей линейногопрограммирования.
Данная дипломная работасостоит из теоретической и практической частей. В теоретической частирассматривается алгоритм решения оптимизационной задачи линейногопрограммирования. В практической части рассматривается задача планированияпроизводства выпускающего несколько видов продукции из ограниченного количестваресурсов для достижения максимальной прибыли. Так же реализуется программныйинтерфейс в среде объектно-ориентированного программирования С++, для решенияпоставленной задачи симплекс методом.
1.Обзор научно-технической литературы
1.1История развития экономико-математического планирования
В 1938-1939 гг.ленинградский математик (впоследствии академик, лауреат Ленинской,Государственных и Нобелевской премий) Л.В. Канторович в результате анализа рядапроблем организации и планирования производства сформулировал новый классусловно-экстремальных задач и предложил методы их решения. Так было положеноначало новой отрасли прикладной математики линейному программированию. В болеепоздних работах Л. В. Канторович расширил область применения линейногопрограммирования в социалистической экономике, сформулировав задачи отраслевогои народнохозяйственного оптимального планирования. А через два десятилетияпосле своего возникновения линейное программирование стало основныминструментом плановоэкономических решений на всех уровнях социалистическогонародного хозяйства.
В том же 1939 г. ленинградский экономист В. В. Новожилов, рассматривая эффективность плановых и проектныхрешений, сформулировал важные теоретические положения, ставшие потоморганической частью теории оптимального планирования социалистической экономики.
Далее методы планированияпродолжали совершенствоваться, но только развитие вычислительной техники вконце 50-х гг. позволило сделать плановые многовариантные расчеты достаточнораспространенными. Важную роль в организации и пропаганде экономико-математическихисследований в этот период сыграл академик В. С. Немчинов. Именно в эти годыполучают развитие некоторые разделы прикладной математики, связанные с решениемоптимизационных задач: линейное и нелинейное программирование, теорияоптимального управления и др. В 60-е гг. основное внимание исследователейсосредоточивается на разработке оптимизационных моделей различных типов и ихпрактическом применении к решению задач планирования. Было построено большоеколичество экономико-математических моделей, на основе которых проведенырасчеты по составлению реальных оптимальных планов (оптимальные планыперевозок, эксплуатации подвижного состава транспорта, использования топлива,загрузки оборудования предприятий; оптимальное размещение отдельных отраслей промышленностии предприятий отрасли; оптимальное планирование и распределениекапиталовложений и т. д.), что дало большой народнохозяйственный эффект. Нарядус расширением сферы применения математических моделей в экономике ипланировании осуществляется процесс усовершенствования моделей и использованияболее адекватного математического аппарата: переход от статических моделей кдинамическим, от жестко детерминированных к стохастическим моделям, учитывающимслучайность и неопределенность экономических процессов, применение дискретногопрограммирования, методов статистического моделирования, создание новыхалгоритмов, позволяющих решать задачи большой размерности.
1.2Необходимость решения задач линейного программирования
Применениеэкономико-математических методов и моделей позволяет существенно улучшитькачество планирования и получить дополнительный экономический эффект безвовлечения в общественное производство дополнительных ресурсов, что чрезвычайноважно в условиях перехода экономики на преимущественно интенсивный путьразвития.
В настоящее время областьвозможного применения экономико-математических методов в планированиичрезвычайно велика и с каждым годом она расширяется. Однако областьфактического их применения в практике плановых расчетов намного скромнее. Этообъясняется трудностями широкого внедрения экономико-математических методов.
К числу их следуетотнести: сложность определения критерия оптимальности в ряде экономическихзадач; трудности при решении проблемы «встраивания» математических моделей всуществующую систему планирования и управления, приводящие к необходимостисоздания новой технологии планирования, базирующегося на системномиспользовании экономико-математических методов и ЭВМ; стохастический идинамический характер экономических процессов, требующий усложненияиспользуемого математического аппарата и программного обеспечения ЭВМ,увеличения объема вычислений; трудность измерений многих экономических явленийи получения массовой достоверной информации для наполнения разработанныхмоделей; трудность проверки правильности (верификации) экономикоматематическихмоделей, ориентированных не столько на подтверждение действительности, сколькона решение новых социально-экономических задач (это в первую очередь относитсяк моделям планирования и прогнозирования), и т. д.
Но главная трудностьзаключается в сложности моделируемых экономических процессов и явлений.Большинство объектов, изучаемых экономической наукой, может бытьохарактеризовано кибернетическим понятием «сложная система». При изучениисистем недостаточно (а иногда и невозможно) пользоваться методом расчленения наэлементы с последующим изучением этих элементов в отдельности.
Кроме того, моделированиесущественно усложняется тем, что экономика охватывает не толькопроизводственные процессы, но и производственные отношения. Моделировать производственныеотношения невозможно, не учитывая поведение людей, их интересы и индивидуальнопринятые решения.
В результатепроизводственно-хозяйственная или социально-экономическая ситуация, в которойприходится принимать плановые решения, часто оказывается намного богаче исложнее тех моделей, которые используются в планировании в этой ситуации.
В настоящее время линейноепрограммирование является одним из наиболее употребительных аппаратовматематической теории оптимального принятия решений, в том числе и в финансовойматематике. Для решения задач линейного программирования разработано сложноепрограммное обеспечение, дающее возможность эффективно и надежно решать практическиезадачи больших объемов. Эти программы и системы снабжены развитыми системамиподготовки исходных данных, средствами их анализа и представления полученныхрезультатов. В развитие и совершенствование этих систем вложен труд и талантмногих математиков, аккумулирован опыт решения тысяч задач. Владение аппаратомлинейного программирования необходимо каждому специалисту в области прикладнойматематики.
Линейное программированиепредставляет собой наиболее часто используемый метод оптимизации. К числу задачлинейного программирования можно отнести задачи:
рациональногоиспользования сырья и материалов; задачи оптимального раскроя;
оптимизациипроизводственной программы предприятий;
оптимального размещения иконцентрации производства;
составления оптимальногоплана перевозок, работы транспорта;
управленияпроизводственными запасами;
и многие другие,принадлежащие сфере оптимального планирования.
Для большого количествапрактически интересных задач целевая функция выражается линейно – черезхарактеристики плана, причем допустимые значения параметров подчинены линейнымравенствам или неравенствам. Нахождение при данных условиях абсолютногоэкстремума целевой функции носит название линейного программирования.
Первым исследованием полинейному программированию является работа Л. В. Канторовича “Математическиеметоды организации и планирования производства”, опубликованная в 1939 г. В нем дана постановка задач линейного программирования, разработан метод разрешающихмножителей решения задач линейного программирования и дано его теоретическоеобоснование.
Прямая задача линейногопрограммирования является математической формулировкой проблемы составлениятакого плана использования различных способов производства, который позволяетполучить максимальное количество однородного продукта при имеющихся в наличииресурсах.
Математическоепрограммирование – это прикладная отрасль математики, которая являетсятеоретической основой решения задач оптимального планирования.
Существуют следующиеразделы математического программирования: линейное, параметрическое, нелинейноеи динамическое программирование. Наиболее разработанным и широко применяемымразделом математического программирования является линейное программирование,целью которого служит отыскивание оптимума (max, min) заданной линейной функциипри наличии ограничений в виде линейных уравнений или неравенств.
1.3Линейное программирование
Линейное программирование— математическая дисциплина, посвященная теории и методам решения задач обэкстремумах линейных функций на множествах n-мерного векторного пространства,задаваемых системами линейных уравнений и неравенств.
Линейное программированиеявляется частным случаем выпуклого программирования, которое в свою очередь являетсячастным случаем математического программирования. Одновременно оно — основанескольких методов решения задач целочисленного и нелинейного программирования.Одним из обобщений линейного программирования является дробно-линейноепрограммирование.
Многие свойства задачлинейного программирования можно интерпретировать также как свойствамногогранников и таким образом геометрически формулировать и доказывать их.
Термин «программирование»нужно понимать в смысле «планирования». Он был предложен в середине 1940-хгодов Джорджем Данцигом, одним из основателей линейного программирования, ещедо того, как компьютеры были использованы для решения линейных задачоптимизации.
1.4Математическая формулировка задачи линейного программирования
Нужно определить максимумлинейной целевой функции (линейной формы)
/>
при условиях
/> при />.
Иногда на xi такженакладывается некоторый набор ограничений в виде равенств, но от них можноизбавиться, последовательно выражая одну переменную через другие и подставляяее во всех остальных равенствах и неравенствах (а также в функции f).
Такую задачу называют«основной» или «стандартной» в линейном программировании.
1.5Постановка задачи целочисленного программирования
По смыслу значительнойчасти экономических задач, относятся к задачам линейного программирования,компоненты решения должны выражаться в целых числах, т.е. быть целочисленными.К ним относятся, например, задачи, в которых переменные означают количествоединиц неделимой продукции, число станков при загрузке оборудования, числосудов при распределениях по линиям, число турбин в энергосистеме, числовычислительных машин в управляющем комплексе и многие другие.
Задача линейногоцелочисленного программирования формируется следующим образом: найти такоерешение (план) X = (x1,x2,...,xn), при котором линейная функция
/>(1)
принимает максимальное илиминимальное значение при ограничениях
/>=bi, i=1, 2…,m. (2)
хj ³ 0, j=1, 2,...,n.(3)
xj — целые числа (4)
2.Обзор основных алгоритмов решения задач ЛП
2.1Целочисленное линейное программирование — метод отсечений Гомори
Целочисленное линейноепрограммирование (сокращенно ЦЛП) занимается задачами линейногопрограммирования с целочисленными переменными, общая задача формулируетсяследующим образом: найти max{сх|Ах ≤ b; х — целочисленный}. ЦЛП можетрассматриваться так же, как поиск точки решетки, принадлежащей многогранникуили как решение системы линейных уравнений с целыми неотрицательнымипеременными. Иными словами, в ЦЛП рассматриваются совместные ограничениянеотрицательность и целочисленность.
2.1.1Отсечения
С помощью отсеченийвыделяют целочисленные части полиэдров. Метод отсечений был разработан в конце1950-х годов Гомори для решения целочисленных линейных программ с помощьюсимплекс-метода. Метод отсечений оказался полезным и с теоретической точкизрения он дает возможность описать целочисленную оболочку полиэдра.
Далее описывается методотсечений Гомори, дающий алгоритм решения задач целочисленного линейногопрограммирования. Данный метод, который также носит название метода отсекающихплоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейногопрограммирования) в канонической форме.
Описываемая ниже версияалгоритма предназначена для решения полностью целочисленных задач, т.е. таких,у которых все параметры aij, cj, bi – целые.
2.1.2Описание алгоритма
Приведем обобщенную схемуалгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждаябольшая итерация содержит этапы:
1.Сначала задача решаетсяметодами линейного программирования (малые итерации), обычно симплекс-методом,и анализируется результат, если результатом являются целые числа, то на этомрешение заканчивается, а если дробные, то производят следующие операции:
2. В оптимальном плане(симплекс-таблице) выбирают строку, в которой целая часть дробного(!)свободного члена (P0) принимает наибольшее значение.
3.Построение для найденнойкомпоненты условия отсечения.
Исходя из уравнения поданной строке xr=P0r — ar,1*x1 — … — ar,n*xn в систему ограничений добавляемнеравенство, в котором коэффициенты будут дробными частями коэффициентовданного уравнения:
{P0r} –{ar,1}*x1 — … -{ar,n}*xn≤ 0.
Переводим к каноническомувиду добавляя новую переменную xn+1, получим:
{P0r} –{ ar,1}*x1 — … — {ar,n}*xn+xn+1= 0
И соответственно добавляемв симплекс-таблицу новый базисный вектор по новой переменной xn+1.
4.Переход на началоследующей большой итерации.
Замечание:
При добавлении в симплекс-таблицунового базисного вектора по новой переменной xn+1 мы получаем недопустимое(отрицательное) решение. Для того, чтобы избавиться от недопустимого решениявыбираем столбец замещения так, чтобы строкой замещения стала новая добавленнаястрока по переменной xn+1. Продолжаем пересчет симплекс-таблицы. Если сноваполучаем дробное решение, то еще вводим дополнительный базисный вектор, и такдо получения целочисленного решения. Но следует заметить, что если областьдопустимых решений очень мала, то она может и не содержать целых значений, этонеобходимо проверить графически. Если область допустимых решений не содержитцелочисленного решения, то в применении метода Гомори нет необходимости, целогорешения не будет!
2.2Целочисленное линейное программирование — метод ветвей и границ
Метод ветвей и границ —общий алгоритмический метод для нахождения оптимальных решений различных задачоптимизации, особенно дискретной и комбинаторной оптимизации. По существу,метод является комбинаторным (алгоритм перебора) с отсевом подмножествмножества допустимых решений, не содержащих оптимальных решений. Его сутьзаключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них,которые оказываются по определенным признакам перспективными, и отбрасываниибесперспективных вариантов.
Метод ветвей и границсостоит в следующем: множество допустимых решений (планов) некоторым способомразбивается на подмножества, каждое из которых этим же способом сноваразбивается на подмножества. Процесс продолжается до тех пор, пока не полученооптимальное целочисленное решение исходной задачи.
Метод был впервыепредложен Ленд и Дойг в 1960 г. для решения задач целочисленного линейногопрограммирования.
2.2.1Общее описание
Общая идея метода можетбыть описана на примере поиска минимума и максимума функции f(x) на множестведопустимых значений x. Функция f и x могут быть произвольной природы. Дляметода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок(границ).
Процедура ветвлениясостоит в разбиении области допустимых решений на подобласти меньших размеров.Процедуру можно рекурсивно применять к подобластям. Полученные подобластиобразуют дерево, называемое деревом поиска или деревом ветвей и границ. Узламиэтого дерева являются построенные подобласти.
Процедура нахожденияоценок заключается в поиске верхних и нижних границ для оптимального значенияна подобласти допустимых решений.
В основе метода ветвей играниц лежит следующая идея (для задачи минимизации): если нижняя граница дляподобласти A дерева поиска больше, чем верхняя граница какой-либо ранеепросмотренной подобласти B, то A может быть исключена из дальнейшегорассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценокзаписывают в глобальную переменную m; любой узел дерева поиска, нижняя границакоторого больше значения m, может быть исключен из дальнейшего рассмотрения.
Если нижняя граница дляузла дерева совпадает с верхней границей, то это значение является минимумомфункции и достигается на соответствующей подобласти.
2.2.2Применение
Метод используется длярешения некоторых NP-трудных задач, такие как:
Задача коммивояжера
Задача о ранце
2.2.3Алгоритм решения
Первоначально находимсимплексным методом или методом искусственного базиса оптимальный план задачибез учета целочисленности переменных. Пусть им является план X0. Если средикомпонент этого плана нет дробных чисел, то тем самым найдено искомое решениеданной задачи и Fmax = F(Xo).
Если же среди компонентплана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленностии необходимо осуществить упорядоченный переход к новым планам, пока не будетнайдено решение задачи. Покажем, как это можно сделать, предварительно отметив,что F(X0) ³ F(X)для всякого последующего плана X.
Предполагая, что найденныйоптимальный план X0 не удовлетворяет условию целочисленности переменных, темсамым считаем, что среди его компонент есть дробные числа. Пусть, например,переменная /> принялав плане X0 дробное значение. Тогда в оптимальном целочисленном плане еезначение будет по крайней мере либо меньше или равно ближайшему меньшему целомучислу />,либо больше или равно ближайшему большему целому числу />+1. Определяя эти числа, находимсимплексным методом решение двух задач линейного программирования:
/>
/>
Найдем решение задачлинейного программирования (I) и (II). Очевидно, здесь возможен один изследующих четырех случаев:
1. Одна из задач неразрешима,а другая имеет целочисленный оптимальный план. Тогда этот план и значениецелевой функции на нем и дают решение исходной задачи.
2. Одна из задачнеразрешима, а другая имеет оптимальный план, среди компонент которого естьдробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном планевыбираем одну из компонент, значение которой равно дробному числу, и строим двезадачи, аналогичные задачам (I) и (II).
3. Обе задачи разрешимы.Одна из задач имеет оптимальный целочисленный план, а в оптимальном планедругой задачи есть дробные числа. Тогда вычисляем значения целевой функции наэтих планах и сравниваем их между собой. Если на целочисленном оптимальномплане значение целевой функции больше или равно ее значению на плане, средикомпонент которого есть дробные числа, то данный целочисленный план являетсяоптимальным для исходной задачи и он вместе со значением целевой функции на немдает искомое решение.
Если же значение целевойфункции больше на плане, среди компонент которого есть дробные числа, тоследует взять одно из таких чисел и для задачи, план которой рассматривается,необходимо построить две задачи, аналогичные (I) и (II).
4. Обе задачи разрешимы, исреди оптимальных планов обеих задач есть дробные числа. Тогда вычисляемзначение целевой функции на данных оптимальных планах и рассматриваем ту иззадач, для которой значение целевой функции является наибольшим. В оптимальномплане этой задачи выбираем одну из компонент, значение которой является дробнымчислом, и строим две задачи, аналогичные (I) и (II).
Таким образом, описанныйвыше итерационный процесс может быть представлен в виде некоторого дерева, накотором исходная вершина отвечает оптимальному плану Х0 задачи (1)-(3), акаждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и(II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шагевыбирается та вершина, для которой значение функции является наибольшим. Еслина некотором шаге будет получен план, имеющий целочисленные компоненты, изначение функции на нем окажется больше или равно, чем значение функции вдругих возможных для ветвления вершинах, то данный план является оптимальнымпланом исходной задачи целочисленного программирования и значение целевойфункции на нем является максимальным.
Итак, процесс нахождениярешения задачи целочисленного программирования (1)-(4) методом ветвей и границвключает следующие основные этапы:
1). Находят решение задачилинейного программирования (1)-(3).
2). Составляютдополнительные ограничения для одной из переменных, значение которой воптимальном плане задачи (1)-(3) является дробным числом.
3). Находят решение задач(I) и (II), которые получаются из задачи (1)-(3) в результате присоединениядополнительных ограничений.
4). В случае необходимостисоставляют дополнительные ограничения для переменной, значение которой являетсядробным, формулируют задачи, аналогичные задачам (I) и (II), и находят ихрешение.
Итерационный процесспродолжают до тех пор, пока не будет найдена вершина, соответствующаяцелочисленному плану задачи (1)-(3) и такая, что значение функции в этойвершине больше или равно значению функции в других возможных для ветвлениявершинах.
Описанный выше методветвей и границ имеет более простую логическую схему расчетов, чем методГомори.
В узлах метода ветвей играниц используется симплекс-метод.
Главный недостатокалгоритма метода ветвей и границ заключается в необходимости полностью решатьзадачи линейного программирования, ассоциированные с каждой из вершинмногогранника допустимых решений. Для задач большой размерности это требуетзначительных и, в известной степени, неоправданных с практической точки зрениязатрат времени.
2.3Симплекс метод
Задачи линейногопрограммирования в канонической форме широко распространены в инженернойпрактике, и для их решения разработана большая группа методов, основной изкоторых — симплекс-метод. Рассмотрим постановку и решение задачи линейногопрограммирования в канонической форме.
2.3.1Описание
Задача будетрассматриваться в форме, которая называется канонической. Известно, что путемвведения дополнительных ограничений и переменных можно свести к каноническойформе задачу линейного программирования, представленную в любой форме, вчастности в естественной форме.
2.3.2Алгоритм симплекс-метода
2.3.2.1Усиленная постановка задачи
Задачи линейногопрограммирования имеет следующий вид:
/>
с помощьюконечно-сходящейся вычислительной процедуры симплекс-метода, заданнойоператором
/>
В операторе векторы /> и /> — оптимальноерешение задачи и начальное приближение для симплекс-метода, которые всимплекс-методе являются базисными решениями, определяемыми ниже. Векторы /> и /> представляютсобой последующее и предыдущее решения в симплекс-методе.
2.3.2.2Алгоритм
Алгоритм симплекс-методаформулируется для задачи линейного программирования следующим образом:
Шаг 1. Формулировка задачилинейного программирования в канонической форме на основе метода искусственногобазиса, так чтобы в матрице ограничений существовала единичная базиснаяматрица. Для этого необходимо дополнить матрицу ограничений единичнымистолбцами, которые должны в совокупности с исходными столбцами матрицыограничений обеспечивать существование единичной базисной матрицы. При этоместественным образом должны быть введены соответствующие искусственныепеременные, которые включаются в целевую функцию с большими положительнымивесовыми коэффициентами для задачи на минимум. В результате запишем исходнуюматрицу ограничений />. в симплекс-таблицу(*), акоэффициенты целевой функции /> запишем в строку этой таблицы. Втаблицу(*) также включим компоненты исходного базисного решения, определяемоговектором />
Таблица (*)#№ Базисные столбцы Bs Базисное решение Xs C1 C2 … Cm Cm+1 … Ck … Cn A1 A2 … Am Am+1 … Ak … An 1 A1
/>
/> 1 …
/> …
/> …
/> 2 A2
/>
/> 1 …
/> …
/> …
/> … … … … … … … … … … … … … l Al
/>
/> …
/> …
/> …
/> … … … … … … … … … … … … … m Am
/>
/> … 1
/> …
/> …
/> Оценки
/>
/> …
/>
/> …
/> …
/>
Шаг 2. Вычислениехарактеристических разностей (оценок) по формулам и запись оценок в />-ю строкусимплекс-таблицы.
Шаг 3. Вычисление оценки />, удовлетворяющейусловию:
Если все />, то в соответствии свыполнением критерия оптимальности вектор />— оптимальное решение, и далееследует перейти к шагу 9, иначе — к шагу 4.
Шаг 4. Вычисление новогобазисного решения /> из условия:
/>
Шаг 5. Вычислениекомпонент нового базисного решения /> по формулам:
/>
Шаг 6. Вычислениеэлементов новой симплекс-таблицы для />-й итерации метода по формулам:
/>
Шаг 7. Корректировкасимплекс-таблицы с учетом изменений коэффициентов целевой функции,соответствующих новому базисному решению. Формируем таблицу (**).
Таблица (**)#№ Базисные столбцы
/>
Базисное решение Xs/> C1 C2 … Cm m+1 … Ck … Cn A1 A2 … Am Am+1 … Ak … An 1 A1
/>
/> 1 …
/> …
/> …
/> 2 A2
/>
/> 1 …
/> …
/> …
/> … … … … … … … … … … … … … l Al
/>
/> …
/> …
/> …
/> … … … … … … … … … … … … … m Am
/>
/> … 1
/> …
/> …
/> Оценки
/>
/> …
/>
/> …
/> …
/>
/>/>/>/>/>Шаг8. Переход к шагу 2.
Шаг 9. Остановка,регистрация оптимального решения.
Таким образом,сформулированный алгоритм определяет конечную последовательность шагов, необходимыхдля вычисления оптимального решения.
2.4Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel
Мощным средством анализаданных MS Excel является надстройка Solver (Поиск решения). С ее помощью можноопределить, при каких значениях указанных влияющих ячеек формула в целевойячейке принимает нужное значение (минимальное, максимальное или равноекакой-либо величине). Для процедуры поиска решения можно задать ограничения,причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Длярасчета заданного значения применяются различные математические методы поиска.Вы можете установить режим, в котором полученные значения переменныхавтоматически заносятся в таблицу. Кроме того, результаты работы программымогут быть оформлены в виде отчета.
2.4.1Описание
Программа «Поиск решений»(в оригинале Excel Solver) – дополнительная надстройка табличного процессора MSExcel, которая предназначена для решения определенных систем уравнений,линейных и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которуюможно решить с помощью базовой версии этой программы, ограничивается такимипредельными показателями:
количество неизвестных(decision variable) – 200;
количество формульныхограничений (explicit constraint) на неизвестные – 100;
количество предельныхусловий (simple constraint) на неизвестные – 400.
Разработчик программыSolver, компания Frontline System, уже давно специализируется на разработкемощных и удобных способов оптимизации, встроенных в среду популярных табличныхпроцессоров разнообразных фирм-производителей (MS Excel Solver, Adobe QuattroPro, Lotus 1-2-3).
Высокая эффективность ихприменения объясняется интеграцией программы оптимизации и табличногобизнес-документа. Благодаря мировой популярности табличного процессора MS Excelвстроенная в его среду программа Solver является наиболее распространенныминструментом для поиска оптимальных решений в сфере современного бизнеса.
Средство поиска решенияMicrosoft Excel использует алгоритм нелинейной оптимизации Generalized ReducedGradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University ofTexas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University),алгоритмы симплексного метода и метода «branch-and-bound» для решения линейныхи целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson)и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.
2.4.2Процедура поиска решения
В меню «Сервис» в разделе«Надстройки» необходимо активизировать функцию «Поиск решения».
Создайте таблицу сформулами, которые устанавливают связи между ячейками. (см. Рис.1)
Выделите целевую ячейку,которая должна принять необходимое значение, и выберите команду «Поискрешения». Поле Set Target Cell (Установить целевую ячейку) открывшегосядиалогового окна надстройки Solver (Поиск решения) будет содержать адресцелевой ячейки.
Установите переключателиEqual To (Равной), задающие значение целевой ячейки, — Мах (максимальномузначению), Min (минимальному значению) или Value of (значению). В последнемслучае введите значение в поле справа.
Укажите в поле By ChangingCells (Изменяя ячейки), в каких ячейках программа должна изменять значения впоисках оптимального результата.
Создайте ограничения всписке Subject to the Constraints (Ограничения). Для этого щелкните на кнопкеAdd (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения)определите ограничение.
/>
Рис.2 Диалоговое окнонадстройки «Поиск решения»
Щелкните на кнопке накнопке Options (Параметры), и в появившемся окне установите переключательНеотрицательные значения (если переменные должны быть позитивными числами),Линейная модель (если задача, которую вы решаете, относится к линейныммоделям).
/>
Рис.3 Окно параметровнадстройки «Поиск решения»
Щелкнув на кнопке Solver(Выполнить), запустите процесс поиска решения.
/>
Рис.4 Результаты поискарешения
2.4.3Параметры средства «Поиск решения»
Максимальное время — служитдля ограничения времени, отпущенного на поиск решения задачи. В этом поле можноввести время в секундах, не превышающее 32 767 (примерно девять часов);значение 100, используемое по умолчанию, вполне приемлемо для решениябольшинства простых задач.
Предельное число итераций- управляет временем решения задачи путем ограничения числа вычислительныхциклов (итераций).
Относительная погрешность- определяет точность вычислений. Чем меньше значение этого параметра, тем вышеточность вычислений.
Допустимое отклонение — предназначен для задания допуска на отклонение от оптимального решения, еслимножество значений влияющей ячейки ограничено множеством целых чисел. Чембольше значение допуска, тем меньше времени требуется на поиск решения.
Сходимость — применяетсятолько к нелинейным задачам. Когда относительное изменение значения в целевойячейке за последние пять итераций становится меньше числа, указанного в полеСходимость, поиск прекращается.
Линейная модель — служитдля ускорения поиска решения путем применения к задаче оптимизации линейноймодели. Нелинейные модели предполагают использование нелинейных функций, факторароста и экспоненциального сглаживания, что замедляет вычисления.
Неотрицательные значения — позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которыхне было задано соответствующее ограничение в диалоговом окне Добавить ограничение.
Автоматическоемасштабирование — используется, когда числа в изменяемых ячейках и в целевойячейке существенно различаются.
Показывать результатыитераций — приостанавливает поиск решения для просмотра результатов отдельныхитераций.
Загрузить модель — послещелчка на этой кнопке отрывается одноименное диалоговое окно, в котором можноввести ссылку на диапазон ячеек, содержащих модель оптимизации.
Сохранить модель — служитдля отображения на экране одноименного диалогового окна, в котором можно ввестиссылку на диапазон ячеек, предназначенный для хранения модели оптимизации.
Оценка линейная — выберитеэтот переключатель для работы с линейной моделью.
Оценка квадратичная — выберите этот переключатель для работы с нелинейной моделью.
Разности прямые — используетсяв большинстве задач, где скорость изменения ограничений относительно невысока.Увеличивает скорость работы средства Поиск решения.
Разности центральные — используется для функций, имеющих разрывную производную. Данный способ требуетбольше вычислений, однако его применение может быть оправданным, если выданосообщение о том, что получить более точное решение не удается.
Метод поиска Ньютона — требует больше памяти, но выполняет меньше итераций, чем в методе сопряженныхградиентов.
Метод поиска сопряженныхградиентов — реализует метод сопряженных градиентов, для которого требуетсяменьше памяти, но выполняется больше итераций, чем в методе Ньютона. Данныйметод следует использовать, если задача достаточно большая и необходимоэкономить память или если итерации дают слишком малое отличие впоследовательных приближениях.
В результате исследованияосновных алгоритмов решения задач ЛП, было принято решение поставленную задачупланирования производства решать симплекс методом. Это обусловлено тем, чтосимплекс метод является эффективным алгоритмом и наиболее универсальным методом,которым можно решить любую задачу линейного программирования. В качествевспомогательного средства, для составления конкретной задачи планированияпроизводства (подбора таких значений, чтобы задача имела решение) былоиспользовано средство «Поиск решения» в MS Excel.
3.Задача планирования производства
Задача планированияпроизводства относится к категории экономических проектов, к которымпредъявлены определенные требования. Проект — это ограниченное по временицеленаправленное изменение отдельной системы с установленными требованиями ккачеству результатов, возможными рамками расхода средств и ресурсов испецифической организацией.
/>/>3.1 Постановка задачипланирования производства в общем случае
Некоторое предприятиепроизводит n типов продукции, затрачивая при этом m типов ресурсов. Известныследующие параметры: aij – количество i-го ресурса, необходимое дляпроизводства единичного количества j-й продукции; aij/>0 (i=1,…,m; j=1,…,n);
bi-запас i-го ресурса напредприятии, bi>0;
cj-цена единичногоколичества j-й продукции, cj>0.
Предполагается, чтозатраты ресурсов растут прямо пропорционально объему производства. Пусть xj –планируемый объем производства j-й продукции. Тогда допустимым является толькотакой набор производимой продукции x=(x1,x2,…,xn), при котором суммарныезатраты каждого вида i-го ресурса не превосходят его запаса:
/> (1)
Кроме того, имеемследующее ограничение: xj/>0; j=1,…,n. (2)
Стоимость набора продукцииx выражается величиной: /> (3)
Задача планированияпроизводства ставится следующим образом: среди всех векторов x, удовлетворяющимограничениям (1), (2), найти такой, при котором величина (3) принимаетнаибольшее значение.
/>/>3.2 Математическое описаниепоставленной задачи планирования симплекс методом
Пусть некотороепредприятие производит 5 видов продукции A, B, C, D и E, затрачивая при этом 5типов ресурсов. На производство продукции типа A требуется следующее количествоимеющихся на предприятии ресурсов (дается количество каждого ресурса,необходимого для производства единицы продукции типа A): 1 – количество ресурса1, 4 – количество ресурса 2, 2 – количество ресурса 3, 1 – количество ресурса4, 3 – количество ресурса 5. На производство единицы продукции типа B требуется(в условных единицах): 2 – количество ресурса 1, 2 – количество ресурса 2, 1 –количество ресурса 3, 4 – количество ресурса 4, 2 – количество ресурса 5. Напроизводство единицы продукции типа C требуется (в условных единицах): 4 –количество ресурса 1, 1 – количество ресурса 2, 3 – количество ресурса 3, 1 –количество ресурса 4, 2 – количество ресурса 5. На производство единицыпродукции типа D требуется (в условных единицах): 3 – количество ресурса 1, 2 –количество ресурса 2, 4 – количество ресурса 3, 2 – количество ресурса 4, 1 –количество ресурса 5. На производство единицы продукции типа E требуется (вусловных единицах): 1 – количество ресурса 1, 2 – количество ресурса 2, 1 –количество ресурса 3, 4 – количество ресурса 4, 4 – количество ресурса 5.
Допустим, что запасресурса 1 на предприятии составляет 600 условных единиц, запас ресурса 2 – 590условных единиц, запас ресурса 3 – 750 условных единиц, запас ресурса 4 – 670условных единиц и запас ресурса 5 – 495 условных единиц.
Цена единицы продукциитипа A равна 60 рублям, цена единицы продукции типа B равна 50 рублям, ценаединицы продукции типа C равна 37 рублям, цена единицы продукции типа D равна45 рублям, а единица продукции типа E – 56 рублям.
Нужно спланировать такойнабор производимой продукции x=(x1, x2, x3, x4, x5), при котором суммарныезатраты каждого вида ресурса не превосходят его запаса, т.е.
x1+4x2+2x3+1x4+3x5/>600;
2x1+2x2+x3+4x4+2x5/>590;
4x1+x2+3x3+x4+2x5/>750;
3x1+2x2+4x3+2x4+x5/>670;
x1+2x2+x3+4x4+4x5/>495;
и при этом должнывыполняться следующие ограничения: x1, x2, x3, x4, x5 /> 0. Спланированный наборпроизводимой продукции x=(x1, x2, x3, x4, x5) должен обеспечить максимумстоимости данного набора
{60x1+50x2+37x3+45x4+56x5}/>max.
Таким образом, мы получимоднокритериальную задачу, которая является задачей линейного программирования(ЗЛП). Она сводится к поиску экстремума линейной функции (данная функцияназывается либо критерием, либо целевой функцией)
f(x)=60x1+50x2+37x3+45x4+56x5
при наличии системылинейных неравенств, ограничивающих область изменения аргументов этой функции
x1+4x2+2x3+1x4+3x5/>600;
2x1+2x2+x3+4x4+2x5/>590;
4x1+x2+3x3+x4+2x5/>750;
3x1+2x2+4x3+2x4+x5/>670;
x1+2x2+x3+4x4+4x5/>495;
x1, x2, x3, x4, x5 /> 0.
3.3Решение поставленной задачи планирования производства
Описание метода решениязадачи.
Процедура решения ЗЛПначинается с приведения ее к канонической форме, то есть к стандартной формезадания, ориентированной на разработанный именно для этой формы метод решения.Задача линейного программирования в канонической форме имеет смысл при условииn>m. В этом случае полностью описывается область допустимых решений (ОДР)ЗЛП, геометрически являющуюся выпуклым многогранником в евклидовом пространствеRn[1]. Выпуклая фигура, как известно, характеризуется тем свойством, что, еслидве точки X1 и X2 принадлежат этой фигуре, то и весь отрезок X1X2 принадлежитей. Кроме того, доказано, что оптимальное решение ЗЛП всегда лежит на границеОДР. Поэтому справедлив вывод о том, что, по крайней мере, одна из угловых(опорных) точек выпуклого многогранника ОДР является точкой оптимума. Для того,чтобы определить координаты опорной точки, все множество переменных X={xj}, j=/>необходиморазделить на два подмножества
/>:
подмножество базисныхпеременных />,при этом число m базисных переменных равно числу уравнений (ограничивается) приусловии, что уравнения являются линейно-независимыми; подмножество /> остальных n-mсвободных (внебазисных) переменных {xj}, j/>Б[1].
Количество возможныхвариантов разделения переменных на базисные и свободные (число базисов) равно />.
Наиболее очевидный методрешения ЗЛП состоит в том, чтобы для каждого из /> базисов найти координатысоответствующих опорных точек, выделить из них точки, принадлежащие ОДР, азатем из них, в свою очередь, выбрать ту, координаты которой максимизируютцелевую функцию. В отличие от этого метода, реализующего, по сути, идею полногоперебора опорных точек ОДР, известен более эффективный так называемыйсимплекс-метод решения ЗЛП.
В основе симплекс-методалежит подход, включающий:
выбор опорной точки,принадлежащей ОДР (выбор начального допустимого базиса);
проверку опорной точки наоптимальность;
выбор нового базиса,позволяющего минимизировать число опорных точек на траектории в случаеневыполнения условий оптимальности.
Приведение исходной задачик каноническому виду.
Имеем исходную ЗЛП:
{60x1+50x2+37x3+45x4+56x5}/>max.
x1+4x2+2x3+x4+3x5/>600;
2x1+2x2+x3+4x4+2x5/>590;
4x1+x2+3x3+x4+2x5/>750;(4)
3x1+2x2+4x3+2x4+x5/>670;
x1+2x2+x3+4x4+4x5/>495;
x1, x2, x3, x4, x5 /> 0.
Приведем ЗЛП кканонической форме. Приведение системы ограничений, заданных в форменеравенств, к канонической форме равенств осуществляется посредствомсоответствующего увеличения размерности вектора X=(x1, x2, x3, x4, x5) с учетомобязательной неотрицательности всех его составляющих.
Таким образом, ЗЛП вканонической форме имеет вид:
max {60x1+50x2+37x3+45x4+56x5};
/> (5)
Поиск допустимого базиса.
Заполнениесимплекс-таблицы.
ЗЛП в канонической формеможно записать в матричном виде:
/>(6)
b=(600, 590,750, 670, 495)T,
X=(x1,x2, x3, x4, x5, x6, x7, x8, x9, x10)T,
C=(60,50,37,45,56,0,0,0,0,0),
A=/>.
Поиск допустимого базисаначинается с анализа столбцов матрицы A=(A1, A2,…, A10), используемой в записиограничения (6) канонической формы ЗЛП. В качестве базисных следует выбиратьтакие 5 переменных, которым соответствует набор столбцов, позволяющих составитьединичную матрицу P=(Aj1, Aj2, Aj3, Aj4, Aj5).
Если ОДР исходной ЗЛПзадана в форме неравенств типа /> (как в нашем случае), тоначальный базис может быть сформирован из дополнительных переменных x6, x7, x8,x9, x10, вводимых в систему ограничений с целью приведения ее к каноническойформе равенств. В этом случае матрица P будет единичной.
Таким образом, выберем вкачестве начального базиса XБО=(x6, x7, x8, x9, x10)T, так как столбцы A6, A7,A8, A9, A10 матрицы A образуют единичную матрицу.
Теперь перейдем кзаполнению симплекс-таблицы. Пусть ЗЛП сформулирована в канонической форме (5).Мы выбрали базисные переменные x6, x7, x8, x9, x10. Разрешим систему неравенствв (5) относительно базисных переменных.
Система ограничений вформе Такера примет вид:
x6=600-(x1+4x2+2x3+x4+3x5);
x7=590-(2x1+2x2+x3+4x4+2x5);
x8=750-(4x1+x2+3x3+x4+2x5);(7)
x9=670-(3x1+2x2+4x3+2x4+x5);
x10=495-(x1+2x2+x3+4x4+4x5);
Целевую функцию можнопредставить в виде:
f(x)=f0-(-60x1-50x2-37x3-45x4-56x5),где f0=0.
Симплекс-таблица выглядитследующим образом:
Таблица 1. Исходная симплекстаблица в общем виде b x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x6 b6 a61 a62 a63 a64 a65 a66 a67 a68 a69 a610 x7 b7 a71 a71 a71 a71 a71 a71 a71 a71 a71 a710 x8 b8 a81 a82 a83 a84 a85 a86 a87 a88 a89 a810 x9 b9 a91 a92 a93 a94 a95 a96 a97 a98 a99 a910 x10 b10 a101 a102 a103 a104 a105 a106 a107 a108 a109 a1010 f(x) f0 c1 c2 c3 c4 c5 c6 c7 c8 c9 c10
В нашем случае:
Таблица 2. Исходная симплекстаблица поставленной задачиБП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X6 600 1 4 2 1 3 1 X7 590 2 2 1 4 2 1 X8 750 4 1 3 1 2 1 X9 670 3 2 4 2 1 1 X10 495 1 2 1 4 4 1 Y -60 -50 -37 -45 -56
Составленнаясимплекс-таблица соответствует начальному базису и начальной опорной точке ОДР.Переход к очередной опорной точке в процессе поиска оптимального решениясопровождается составлением новой симплекс-таблицы.
Каждая симплекс-таблицаанализируется по критериям допустимости и оптимальности базиса.
3.3.4Проверка признака допустимости и оптимальности базиса
Признак допустимостибазиса:
в опорной точке всоответствии с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому признак допустимостибазиса формулируется как условие bi/>0, i=6,…,10.
Признак оптимальностибазиса:
Если для /> то найденное решениеоптимально и единственно.
Если для /> то найденное решениеоптимально, но не единственно.
Если /> то решениенеоптимально. В этом случае поиск оптимального решения продолжается инеобходимо перейти к новой опорной точке.
Перейдем к конкретному случаю.В нашем случае выполняется условие допустимости базиса, так как b=(600, 590,750, 670, 495)T
Выбранный нами начальныйбазис XБО=(x6, x7, x8, x9, x10)T не является оптимальным, так как c1=-60
3.3.5Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса
В соответствии ссимплекс-методом новая опорная точка выбирается только среди соседних, то естьновый базис лишь одной переменной отличается от прежнего. Таким образом,формирование нового базиса осуществляется на базе прежнего посредствомвыведения из него одной из базисных переменных xs и введения одной из свободныхпеременных xr.
Выбор переменной xr. Выборпеременной xr осуществляется по результатам анализа коэффициентов cjсимплекс-таблицы. Найдем cr=/>.
В нашем случае min{c1, c2,c3, c4, c5}=c1=-60 и xr=x1.
Столбец, которыйсоответствует переменной xr=x1 в симплекс-таблице, будем называть разрешающим.
Выбор переменной xs. Выборпеременной xs проводится по результатам анализа коэффициентов air i=1,2,3,4,5разрешающего столбца.
Если />, это означает, что ОДРтакова, что неограниченное увеличение свободной переменной xr приводит кнеограниченному возрастанию целевой функции (ОДР не замкнута).
Если />, то соответствующиебазисные переменные xi (i=6,7,8,9,10) получают отрицательные приращения приувеличении xr=x1. Среди этих переменных xi необходимо отыскать xs, достигающуюнуля при минимальном значении приращения xr. Нужно найти
/>.
В нашем случае min{600/1,590/2, 750/4, 670/3, 495/1}=min{600,295,187.5,223.3,495}=187.5 и xs=x8. Строка,которая соответствует переменной xs=x8 в симплекс-таблице, называетсяразрешающей. Элемент asr=a81=4 называется разрешающим элементомсимплекс-таблицы.
Выбор разрешающегоэлемента завершает формирование нового базиса XБ1, отличающегося от прежнегобазиса одной переменной xr=x1, то есть вместо переменной x8 в базис XБ1 будетвключена переменная x1: XБ1=(x6, x7, x1, x9, x10)T.
Для нового базиса (новойопорной точки) снова заполняется симплекс-таблица, в которой новые базисныепеременные выражены через новые свободные.
3.3.6Пересчет симплекс-таблицы
Правила пересчета:
Разрешающий элементзаменяется на 1.
Элементы разрешающегостолбца за исключением asr переписываются без изменений.
Элементы разрешающейстроки за исключением asr изменяют знак на противоположный.
Оставшиеся элементы новойсимплекс-таблицы вычисляются согласно следующему правилу: произведениесоответствующего элемента прежней таблицы на разрешающий элемент asr минус произведениеэлементов, находящихся на другой диагонали таблицы. В соответствии с этимправилом имеем:
/>
Все элементы полученнойтаблицы необходимо разделить на разрешающий элемент asr:
/>
Таблица 3. Итерация №1БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X6 825/2 15/4 5/4 3/4 5/2 1 -1/4 X7 215 3/2 -1/2 7/2 1 1 -1/2 X1 375/2 1 1/4 3/4 1/4 1/2 1/4 X9 215/2 5/4 7/4 5/4 -1/2 -3/4 1 X10 615/2 7/4 1/4 15/4 7/2 -1/4 1 Y 11250 -35 8 -30 -26 15
XБ1=(x6, x7, x1, x9, x10)T.
Базис XБ1=(x6, x7, x1, x9,x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a92=5/4определяет необходимость перехода к базису XБ2=(x6, x7, x1, x2, x10)T. Приведемрезультат пересчета симплекс-таблицы для базиса XБ2.
Таблица 4. Итерация №2. БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X6 90 -4 -3 4 1 2 -3 X7 86 -13/5 2 8/5 1 2/5 -6/5 X1 166 1 2/5 3/5 2/5 -1/5 X2 86 1 7/5 1 -2/5 -3/5 4/5 X10 157 -11/5 2 21/5 4/5 -7/5 1 Y 14260 57 5 -40 -6 28
Базис XБ2=(x6, x7, x1, x2,x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицы a65=4определяет необходимость перехода к базису XБ3=( x5, x7, x1, x2, x10)T.Приведем результат пересчета симплекс-таблицы для базиса XБ3.
Таблица 5. Итерация №3БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X5 45/2 -1 -3/4 1 1/4 1/2 -3/4 X7 50 -1 16/5 -2/5 1 -2/5 X1 305/2 1 1 9/20 -3/20 1/10 1/4 X2 95 1 1 7/10 1/10 -2/5 1/2 X10 125/2 2 103/20 -21/20 -13/10 7/4 1 Y 15160 17 -25 10 14 -2
Базис XБ3=(x5, x7, x1, x2,x10)T является допустимым, но не оптимальным. Разрешающий элемент таблицыa104=103/20 определяет необходимость перехода к базису XБ4=(x5, x7, x1, x2,x4)T. Приведем результат пересчета симплекс-таблицы для базиса XБ4.
Таблица 6. Итерация №4БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X5 3255/103 -73/103 1 10/103 32/103 -51/103 15/103 X7 1150/103 -231/103 26/103 1 42/103 -112/103 -64/103 X1 15145/103 1 85/103 -6/103 22/103 10/103 -9/103 X2 8910/103 1 75/103 25/103 -23/103 27/103 -14/103 X4 1250/103 40/103 1 -21/103 -26/103 35/103 20/103 Y 15463,4 2751/103 505/103 792/103 669/103 500/103
Анализ Таблицы 6 позволяетсделать вывод о допустимости и оптимальности базиса XБ4=(x5, x7, x1, x2, x4)T.
3.4Результат решения задачи планирования производства
В результате решенияпоставленной задачи симплекс-методом получили набор производимой продукцииx=(x1, x2, x3, x4, x5)=( 15145/103, 8910/103, 0, 1250/103, 3255/103), которыйудовлетворяет всем наложенным ограничениям и обеспечивает максимальнуюстоимость данного набора (максимум целевой функции f(x)=60x1+50x2+37x3+45x4+56x5=15463,4 рублей). Таким образом, можно оптимальноспланировать объем производства продукции при наличии заданного количестваресурсов: продукции типа A нужно выпустить 147 единиц, продукции типа B – 86единиц, продукции типа D – 12 единиц, продукции типа E – 31 единицу, апродукцию типа D – для достижения максимальной прибыли в данных условияхпроизводить не выгодно.
При этом ресурсы типа 1,3, 4, 5 будут использованы полностью, а 11 единиц ресурса типа 2 останутсянеизрасходованными.
4.Программа для решения задач ЛП симплекс методом
4.1Описание
В процессе выполнениядипломной работы был реализован и отлажен программный интерфейс под ОС WindowsXP (также протестирован под Windows Vista), решающий задачи ЛП симплекс методом(в частности поставленную задачу планирования производства).
Программа осуществляет: решениезадач ЛП симплекс методом; сохранение и загрузка исходных данных в файл/изфайла; вывод решения по шагам; экспорт решения в документ MS word; системныйкод программы написан в среде объектно-ориентированного программирования С++.
4.2Графическое представление программы
Главное окно программы«Исходные данные»:
/>
Рис.5 Главное окнопрограммы Simplex: 1 – Кнопки загрузка/сохранение исходных данных в файл. 2 –Число переменных, в нашем случае количество производимой продукции. 3 – Числоограничений, в нашем случае количество запасов ресурсов на складе. 4 – Целеваяфункция, в нашем случае максимизация. 5 – Система ограничений в форме Такера. 6– Кнопка для решения задачи и перехода к окну «Решение».
Окно программы «Решение»: