Симплекс метод

Симплекс  метод

 

Содержание

 

Введение…………………………………………………………………………...3

Глава 1 Теоретические основы………………………………………………...…4

1. Предпосылки возникновения АСУ. Понятие АСУ……………………....4

1.2 Классификация  АСУ…………………………………………………….…5

1.3 Функциональные  задачи и подсистемы АСУ…………………………….6

1.4 Обеспечивающие  подсистемы АСУ…………………………………..…..7

Глава 2. Симплекс метод……………………………………………………..…..9

2.1 Математическое описание метода……………………………………..….9

2.2 Блок  – схема алгоритма…………………………………………………..13

2.3 Пример решения задачи с использованием симплекс-метода…………14

2.4 Текст программы………………………………………………………….16

Глава 3. Практические задания и  подробное решение………………………..25

Заключение…………………………………………………………………….…33

Список использованной литературы…………………………………………...34

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

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

Один  из методов линейного программирования, как раз является симплекс метод, который рассмотрен в моей курсовой работе.

Данный  метод является универсальным, т.е. может быть применен при решении любой задачи линейного программирования. В основе симплексного метода лежит алгоритм симплексных преобразований системы уравнений. Он позволяет, исходя из известного опорного плана (базисного решения) задачи, за конечное число шагов получить ее оптимальный план. Каждый из шагов (итераций) состоит в нахождении нового плана, которому соответствует лучшее (меньшее или большее в зависимости от условия задачи) значение целевой функции, чем значение этой же функции в предыдущем плане. Процесс продолжают до получения оптимального плана.  Если задача не обладает планами или экстремум линейной функции равен то симплексный метод позволяет установить это в процессе решения.

Таким образом, идея симплекс – метода заключается  в последовательном улучшении плана.

 

 

 

Глава 1 Теоретические основы.

1. Предпосылки возникновения АСУ. Понятие АСУ.

АСУ – это комплекс технических и программных средств, обеспечивающих тесные взаимодействия организационной структуры (отдельных людей, коллективов) и управление объектом в производственной, научной или общественных сферах.

Первые  АСУ  имели недостатки, так как  они копировали ручной труд, который  применялся до внедрения АСУ. В связи  с этим внедрение первых АСУ имели  неудачи, так как они копировали тот беспорядок, который имел место  в управлении производством до их внедрения и способствовали дезорганизации производства. Тем ни менее для  тех функциональных  задач, где  имелись достаточно формализованные  алгоритмы (задачи финансового учета, материально технического снабжения  и другое) внедрение АСУ позволило  значительно улучшить отчетность, контроль прохождения документации, своевременность  принятия решения, что во многих случаях  дало значительный экономический эффект.

Качество  управления непосредственно связано  с применением математических методов, внедрение которых без ЭВМ  невозможно из-за больших вычислительных работ.

К математическим методам в первую очередь относятся  – оптимизационные методы, статистическая обработка информации, математическое моделирование и т.д. Еще одним  недостатком в первой АСУ было использование вычислительной техники  более мощной, чем это требовалось  для решения задач. Развитие автоматизированных систем показало, что необходимо:

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

Опыт  разработки и внедрения АСУП показал  высокую экономическую эффективность (хорошая организация труда и  производства, повышения точности планирования, уменьшение доли ручного труда). Для  разработки АСУ необходимо хорошо знать  экономико – математические методы управления, отлично представлять организацию производства знать основы теории автоматизированного производства, информатику, уметь проектировать систему на базе СУБД.

 

1.2 Классификация АСУ.

АСУ различают  по результатам деятельности и по выполняемым функциям.

По функциям:

1. Административно – организационные (АСУП (предприятий), ОАСУП (отраслевые)).
2. АСУТП (технологическими процессами). К ним относятся гибкие производственные системы, системы контроля качества продукции, системы управления станками с ЧПУ (числовые программные управления).
3. Интегрированные системы объединяющие перечисленные АСУ в различных комбинациях.

Первые АСУТП были введены в 70-х годах. Наибольшее количество таких  систем было внедрено в химическую и нефтехимическую промышленность, в черную и цветную металлургию, в энергетику. Созданные АСУТП  были по своему характеру автоматизированными  системами, в них значительная роль отводилась оператору, который по информации предоставленной ЭВМ принимала  решение либо сам, либо выполнял решение  подсказанное ЭВМ.

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

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

1. Концептуальный – дает качественное описание системы (что может?)
2. Логический – позволяет на основе математического аппарата формализовать, логически определить место отдельных элементов в системы в пространстве и оценить их взаимодействие во времени.
3. Физический – позволяет судить о возможностях реализации системы на основе различных аппаратно-программных средств.

 

1.3 Функциональные задачи и подсистемы АСУ.

Современная АСУ является многоуровневой. Анализ и синтез такой системы может  быть выполнен на основе теории многоуровневых иерархических систем. В соответствии с этой теорией систему можно  разделить на подсистемы и далее  на задачи, что позволяет разделить  общие цели управления на отдельные  подцели, реализуемые подсистемами. Метод иерархической декомпозиции является основным методом исследования сложных систем управления. Разделение системы по функциональному признаку приводит к выделению функциональных частей АСУ, которые получили название функциональных подсистем. Функциональные подсистемы делятся на функциональные задачи. Такая последовательность действий является естественной при анализе  создаваемой АСУ. Однако на этапе  синтеза создание и внедрение  исходной является некоторая организационно-экономическая  модель, включающая в себя функции  и уровни управления, разделение этих функций по производственным подразделениям с внедрением отдельных задач  управления. На этом этапе необходимо определить множество функций управления, которые подлежат автоматизации, оценить  целесообразные уровни управления и  если необходимо выделить стадии управления производством, которые охватываются автоматизацией. При создании АСУ  важно экономно расходовать вычислительный ресурс, а поэтому данные задачи являются оптимизационными. В качестве ограничений выступает вычислительный ресурс. Для упорядочения решаемых задач необходимо их совместить с  соответствующими уровнями управления, которые являются достаточно определенными  для каждого типа предприятия. Основными  уровнями управления является перспективное  планирование, управление подготовкой  производства, технико-экономическое  планирование и общезаводское производственное планирование и управление (оперативное  управление). На уровне перспективного планирования можно выделить ряд  функций управления, которые подлежат автоматизации. Одной из основных функций  на этом уровне выступает прогнозирование. Применительно к отраслевой АСУ  прогнозирование может касаться целого ряда экономических показателей, связанных с развитием отрасли. Для АСУП прогнозирование относиться к выпускаемой продукции, к потребности  предприятия в каких-то видах  сырья, изделий. Решение этих задач  в основном базируется на оценке экономического процесса, ранее имевшего место в  деятельности предприятия и экстраполяции  этого опыта на будущие годы. Вводится ряд функций отображающих зависимость  требуемых экономических показателей  по годам, т. е. Оценивает тенденцию развития на основе принятых математических закономерностей.

Методы  прогнозирования опираются на стационарность экономического процесса, что не всегда имеет место, поэтому чаще используют методы экспертных оценок. Использование  автоматизированного управления для  решения подобных функциональных задач  позволяет осуществить оптимизационную  постановку задач. В качестве критерия принимаются полные приведенные  затраты и минимизируются функциональные затраты. В результате получают рекомендации по функциональному развитию отдельных  отраслей промышленности, оптимальному размещению объектов производства, с  учетом имеющихся людских и энергетических ресурсов. В целом минимизируются суммарные, капитальные эксплутационные затраты на производство (затраты на транспортировку и сырье). На уровне предприятия основной задачей является максимизация прибыли предприятия или обеспечение производства продукции в заданном объеме и ассортименте, при минимуме экономических затрат. Решается ряд частных функциональных задач по определению номенклатуры выпускаемой продукции, строкам ввода отдельных мощностей.

 

1.4 Обеспечивающие подсистемы АСУ.

Выделяемая в соответствии со структурным  подходом обеспечивающая часть АСУ  включает в себя: организационное, информационное, математическое, алгоритмическое, программное, техническое, лингвистическое, правовое и агрономическое обеспечения. Эти  обеспечения создаются на стадии микропроектирования, т. е. Внутреннего  проектирования системы или определяются характеры работ при создании АСУ. А так же взаимосвязь отдельных  подсистем АСУ при функционировании.

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

Линейное  программирование представляет собой  наиболее часто используемый метод  оптимизации. К числу задач линейного  программирования можно отнести  задачи:

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