План производства. 2

Изм.

Лист

№ докум.

Подпись

Дата

Лист

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ………………………………………………………………………..4

1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1. Понятие симплексного метода решения задач линейного программирования…………………………………………………………6

1.2. Порядок работы с симплекс-таблицей……………………………...10

1.3. Двойственная модель линейного программирования……………..12

1.3.1. Построение двойственной  задачи………………………….12

1.3.2. Сравнительная характеристика  прямой и двойственной модели………………………………………………………………15

1.4. Двойственный симплексный  метод…………………………………16

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Содержательная постановка  задачи………………………………...18

2.2. Разработка и описание алгоритма решения задачи

2.2.1. Построение математической  модели задачи……………....19

2.2.2. Решение задачи………………………………………………20

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

2.3.1. Построение двойственной  задачи и ее решение…………..24

2.3.2. Определение статуса  и значимости ресурсов……………...25

2.3.3. Определение интервалов  устойчивости решения…………26

ЗАКЛЮЧЕНИЕ………………………………………………………………….29

БИБЛИОГРАФИЧЕСКОЕ ОПИСАНИЕ…………………………………….....31

ВВЕДЕНИЕ

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

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

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

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

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

Задачи курсовой работы:

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

2. Полученную задачу необходимо решить симплексным методом;

3. Произвести оценку имеющихся ресурсов с помощью двойственной задачи;

4. Произвести анализ устойчивости полученных двойственных оценок.

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

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

1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1. Понятие симплексного  метода решения задач линейного  программирования

Симплексный метод представляет собой итерационный способ нахождения решения, заключающийся в постепенном  переходе от одного решения к другому  до нахождения оптимума задачи. [2]

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

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

Этот метод является универсальным, применимым к любой задаче линейного  программирования в канонической форме. Система ограничений здесь – система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен , то мы можем выбрать неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные , ,….Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно  выражать через остальные первые неизвестных. Однако такие неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через  свободные), мы будем получать различные  решения нашей системы ограничений. Таким образом, можно получить любое  ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны  нулю. Такие решения называются базисными, их столько же, сколько различных  базисных видов у данной системы  ограничений. Базисное решение называется допустимым базисным решением или опорным  решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные , ,…, то решение будет опорным при условии, что .

Симплекс-метод основан  на теореме, которая называется фундаментальной  теоремой симплекс-метода. Среди оптимальных  планов задачи линейного программирования в канонической форме обязательно  есть опорное решение ее системы  ограничений. Если оптимальный план задачи единственен, то он совпадает  с некоторым опорным решением. Различных опорных решений системы  ограничений конечное число. Поэтому  решение задачи в канонической форме  можно было бы искать перебором опорных  решений и выбором среди них  того, для которого значение самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом. [5]

Итак, симплексный метод  вносит определенный порядок как  при нахождении первого (исходного) базисного решения, так и при  переходе к другим базисным решениям. Его идея состоит в следующем.

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

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

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

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

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

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

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

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять  переменные , ,… и что при этом (соответствующее базисное решение является опорным).

Для составления симплекс-таблицы  во всех равенствах в условии задачи члены, содержащие переменные, переносятся  в левую часть, свободные оставляются  справа, т.е. задача записывается в виде системы равенств:

Далее эта система оформляется  в виде симплекс-таблиц (табл. 1.1).

Таблица 1.1

Симплекс-таблица

1.2. Порядок работы с симплекс-таблицей

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

Алгоритм перехода к следующей таблице такой:

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

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

- среди выбранных коэффициентов  столбца выбирается тот, для  которого абсолютная величина  отношения соответствующего свободного  члена (находящегося в столбце  свободных членов) к этому элементу  минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится – ключевой; [5]

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

- разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.

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

- в новой таблице все элементы ключевого столбца равны 0, кроме разрезающего, он всегда равен 1.

- столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же.

- строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

-  в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

В результате получают новую  симплекс-таблицу, отвечающую новому базисному  решению.

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

1.3. Двойственная модель линейного программирования

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

На основе теории двойственности разработан алгоритм решения задач линейного программирования – двойственный симплексный метод и эффективные методы анализа моделей на чувствительность.

1.3.1. Построение двойственной  задачи

Двойственная обратная задача – задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной, или прямой, задачи. [1]

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

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

Прямая задача линейного  программирования в стандартной  форме записывается следующим образом:

максимизировать

 (1.4)

при ограничениях:

  (1.5)

Чтобы сформулировать условия  двойственной задачи, проведем симметричное структурное преобразование условий  прямой задачи в соответствии со следующими правилами:

1) каждому ограничению  прямой задачи соответствует  переменная двойственной задачи;

2) каждой переменной прямой  задачи соответствует ограничение  двойственной задачи;

3) коэффициенты при некоторой  переменной, фигурирующие в ограничениях  прямой задачи, становятся коэффициентами  левой части соответствующего  ограничения двойственной задачи, а коэффициент, фигурирующий при  той же переменной в выражении  для целевой функции прямой  задачи, становится постоянной правой  части этого же ограничения  двойственной задачи.

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

Запишем математическую модель двойственной задачи.

Определить вектор , который удовлетворяет ограничениям

  (1.6)

и обеспечивает минимальное  значение целевой функции

 (1.7)

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

В целом двойственная задача по отношению к исходной составляется согласно следующим правилам.

1. Число переменных в  двойственной задаче равно числу  ограничений в прямой задаче.

2. Матрица коэффициентов  системы ограничений двойственной  задачи получается из матрицы  коэффициентов системы ограничений  прямой задачи путем транспонирования.

3. Система ограничений  двойственной задачи записывается  в виде неравенств противоположного  смысла неравенствам системы  ограничений прямой задачи.

4. Свободными членами  системы ограничений двойственной  задачи являются коэффициенты  функции цели прямой задачи.

5. Двойственная задача  решается на минимум, если целевая  функция прямой задачи задается  на максимум, и наоборот.

6. Коэффициентами функции  цели двойственной задачи служат  свободные члены системы ограничений  прямой задачи.

7. Если переменная прямой  задачи , то j-е условие системы ограничений двойственной задачи является неравенством, если – любое число, то j-е условие двойственной задачи представляет собой уравнение.

8. Если i-е соотношение прямой задачи является неравенством, то соответствующая оценка i-го ресурса – переменная , если i-е соотношение представляет собой уравнение, то переменная двойственной задачи – любое число.

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

1.3.2. Сравнительная характеристика прямой и двойственной модели

1) Прямая модель. Переменные модели – это количество каждого продукта, которое необходимо производить каждую неделю. Целевая функция задачи – это общая прибыль, получаемая в неделю от производства продуктов. Каждое ограничение соответствует одному виду сырья. Левая часть каждого ограничения представляет собой общее количество сырья одного вида, требуемое для производства всех видов продуктов. Правая часть ограничений содержит общее количество сырья каждого вида, которое фирма может использовать в течение недели. [2]

2) Двойственная  модель. Переменные модели – это теневые цены ресурсов для прямой модели, т.е. величины, на которые увеличилось бы значение целевой функции при росте имеющегося запаса сырья соответствующего вида на единицу. Теневые цены характеризуют стоимость единицы сырья каждого вида. Целевая функция задачи – это общая еженедельная стоимость всех видов сырья, используемых при производстве продуктов. Каждое ограничение связано с одним из продуктов. В левой части каждого ограничения дана общая стоимость всех видов сырья, используемых при выпуске 1 единицы соответствующего продукта; в правой – прибыль от выпуска единицы соответствующего продукта. [2]

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

1.4. Двойственный симплексный  метод

Двойственный симплексный  метод основан на теории двойственности и используется для решения задач  линейного программирования, свободные  члены которых b_i (i=1,…m) могут принимать любые значения, а система ограничений задана неравенствами смысла «», «» или равенством «=».

В двойственном симплексном  методе оптимальный план получается в результате движения по псевдопланам.

Псевдопланом называется план, в котором условия оптимальности  удовлетворяются, а среди значений базисных переменных x_i имеются отрицательные числа. [1]

Алгоритм двойственного  симплексного метода включает следующие  этапы.

1. Составление  псевдоплана. Систему ограничений исходной задачи требуется привести к системе неравенств смысла «». Для этого обе части неравенств смысла «» необходимо умножить на (−1). Затем от системы неравенств смысла «» переходят к системе уравнений, вводя неотрицательные дополнительные переменные, которые являются базисными переменными. Первый опорный план заносят в симплексную таблицу.

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

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

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

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

4. Расчет нового  опорного плана. Новый план получаем в результате

пересчета симплексной таблицы методом Жордана – Гаусса.

Далее переходим к этапу 2.

2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

2.1. Содержательная постановка  задачи

Китайская компания с ограниченной ответственностью по производству гусеничных механизмов выпускает пять сходных друг с другом товаров – А, В, С и D. В нижеследующей таблице 2.1 представлены расходы ресурсов, необходимых для выпуска единицы каждого товара, а также недельные запасы каждого ресурса и цены продажи единицы каждого продукта.

Таблица 2.1

Исходные данные