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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ  БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ  НЕФТЕГАЗОВЫЙ УНИВЕРСИТЕТ»

 

Кафедра «Автоматизации и вычислительной техники»

 

 

 

 

 

 

 

 

Курсовая работа

 

по дисциплине «Теория  принятия решений»

 

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

и разработка программного обеспечения 

для решения задачи организационного управления»

 

Вариант 7

 

 

 

 

 

 

 

Выполнила:

студентка группы

 

Проверил:

 преподаватель

 

 

 

 

 

 

 

 

Тюмень 2013

 

 

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ………………………………………………………………..….….3

1.Задачи линейного  программирования ………………………………….…..…...4

  1.1 Словесная формулировка задания ………………………………………..5

  1.2 Построение математической модели ………………………………...…...7

2. Решение задач симплекс  методом…………………………………………...…..6

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

  2.2  Реализация  задачи в Excel 2003 ………………………………………....12

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………….........18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

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

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

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

нахождение оптимального плана выпуска продукции (оптимальное  распределение ресурсов);

оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);

определение оптимального рациона (оптимизация состава химической смеси);

транспортная задача (оптимальное распределение потоков  товарных поставок по транспортной сети);

задача о размещении производства (планирование с учетом затрат на производство и транспортировку продукции);

задача о назначениях (оптимальное распределение различных  видов транспортных средств) и др.

В настоящее время  одним из перспективных, но недостаточно распространенных способов численного решения задач линейного программирования является использование надстройки «Поиск решения» электронных таблиц Microsoft Excel. В частности, «Поиск решения» предоставляет возможность:

использования планов большой  размерности (т. е. с большим количеством варьируемых переменных);

задания ограничений  сложного вида;

отыскания оптимального из допустимых решений;

генерирования множества  различных решений, сохраняемых  в дальнейшем в виде сценариев;

автоматического создания отчета по решению задачи.

Теоретической основой  надстройки «Поиск решения» является симплекс-метод, позволяющий находить оптимальное решение задачи планирования с помощью итерационного процесса перехода к улучшающимся планам. «Поиск решения» является дополнением Excel, т. е. может не входить в стандартный вариант установки электронных таблиц. Для его добавления достаточно воспользоваться командой Сервис®Надстройки®Поиск решения

 

 

1. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

 

Задача, в которой фигурируют ограничения в форме неравенств, называется — основной задачей линейного программирования (ОЗЛП)

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

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

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

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

 

 

 

 

 

 

 

 

 

 

1.1Словесная  формулировка задания

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

 

Тип оборудования	Кол-во произведенных  в течение 1 часа изделий вида				Затраты (ден.ед.), связанные  с производством в течение 1-го часа изделий вида
	1	2	3	4	1	2	3	4
I	8	7	4	5	2,7	2,6	2,7	2,4
II	6	8	6	4	2,6	2,7	2,6	2,5

 

Оборудование I типа предприятие может использовать не более 80 часов, а оборудование II типа – не более 60 часов.

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

 

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

 

Сформулируем математическую модель данной задачи. Введем 8 переменных, которые определяют количество времени работы по изготовлению 4 изделий на 2 типах оборудования. Обозначим через x₁, x₂, x₃, x₄ – количество времени, в течении которого I тип  оборудования будет производить изделия 1, 2, 3, 4 вида, а через x₅, x₆, x₇, x₈ – количество времени, в течении которого II тип оборудования будет производить изделия.

Поскольку оборудование I типа предприятие может использовать не более 80 часов, то имеем первое ограничение:

x₁ + x₂ + x₃ + x₄ ≤ 80.

Поскольку оборудование II типа предприятие может использовать не более 60 часов, то имеем второе ограничение:

x₅ + x₆ + x₇ + x₈ ≤ 60.

Далее необходимо обеспечить изготовление изделий каждого вида соответственно не менее 240, 160, 150 и 220 единиц. Следующие ограничения будут такими:

x₁ + x₅ ≥ 240;

x₂ + x₆ ≥ 160;

x₃ + x₇ ≥ 150;

x₄ + x₈ ≥ 220.

Таким образом, имеем  систему линейных неравенств:

 

 

2. РЕШЕНИЕ  ЗАДАЧ СИМПЛЕКСНЫМ МЕТОДОМ

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

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

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

• просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов  ) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
• просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке- ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
• среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка в которой он находится ключевой;
• в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:
• разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
• строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место.
• в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
• столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.
• строка, у которой в ключевом столбце имеется 0,в новой таблице будет такой же.
• в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы:

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение

 

 

Найти значения переменных x₁...x₈, при которых функция:

Q =

27

x1

+

26

x2

+

27

x3

+

24

x4

+

26

x5

+

27

x6

+

26

x7

+

25

x8

 

принимает минимальное значение, при заданных ограничениях:

 

 

 

 

Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4, 5, 6 неотрицательные балансовые переменные s₁, s₂, s₃, s₄, s₅, s₆. Получим следующую систему ограничений:

 

 

Ищем в системе ограничений базисные переменные. 
Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу. 
 
Введем по одной искусственной неотрицательной переменной r_i в каждое уравнение системы ограничений. 
Получим следующую систему ограничений, 
с базисными переменными s₁,s₂,r₁,r₂,r₃,r₄

 

 

x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, s₁, s₂, s₃, s₄, s₅, s₆, r₁, r₂, r₃, r₄ ≥ 0

 

Целью решения вспомогательной  задачи является получение допустимого  базисного решения не содержащего  искусственных переменных (r₁,r₂,r₃,r₄). Для этого сформируем вспомогательную целевую функцию: