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

Изм.

Лист

№ докум.

Подпись

Дата

Лист

 

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ………………………………………………………………………..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	0	…	0			…	…	…
		0	1	…	0			…	…	…
…	…	…	…	…	…	…	…	…	…	…	…
		0	0	…	1			…	…	…
		0	0	…	0			…	…	…

 

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

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

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

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

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