Программирование и основы алгоритмизации (ведение в исследование операций)
Курсовая работа
по дисциплине «Программирование и основы алгоритмизации (введение в исследование операций)»
Содержание
Введение
1. Формализация задач
2. Методы решения
3. Решение задачи
4. Решение задачи в среде MS EXCEL
5. Анализ задачи на чувствительность
Заключение
Литература
Введение
Мебельная фабрика выпускает столы, стулья, платяные и книжные шкафы. При изготовлении этой продукции используется два типа древесных материалов (досок). В таблице приведены нормативные затраты на единицу изделия. Объемы наличных ресурсов каждого типа соответственно равны 1500, 1000, 3200. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно.
Существуют следующие условия: столов необходимо произвести не менее 40, стульев - не менее 120, платяных шкафов - не менее 20, книжных шкафов - не более 20. Определить ассортимент продукции, максимизирующей прибыль фабрики в данных условиях. Запас какого типа досок следует изменить в первую очередь и на сколько для увеличения прибыли.
Таблица 1
РесурсыЗапас ресурсовЗатратыСтолСтулШкаф платянойШкаф книжныйДоски I типа1500511215Доски II типа10003265Труд чел./ч.3200751012Прибыль6025140160
1. Формализация задачи
Операция - обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики, при заданных условиях.
Организация операции.
В качестве параметров, описывающих количество каждого вида продукции, примем:1 - количество столов, x2 - количество стульев, x3 - количество шкафов платяных, x4 - количество шкафов книжных. Единица измерения - штуки. При этом, имеем условные ограничения: количество выпускаемой продукции не может быть отрицательным, и является целым числом: хi≥0, хi-целые числа (i = 1…4).
Оперирующая сторона
Руководство мебельной фабрики, как постановщик задачи. Непосредственный изготовитель продукции (трудовой ресурс) - лица, изготовляющие мебель. Покупатель (или заказчик) - лицо, обеспечивающее существование имеющейся цели. Поставщик материала (используемого ограниченного ресурса) - лицо, принимающее участие в процессе достижения цели.
Лицо, принимающее решение (ЛПР) - индивид или группа людей, которые осуществляют выбор и несут ответственность за принятое решение в соответствии со своими полномочиями, установленными руководством фирмы.
Исследователь операций - лицо, чья работа состоит в рациональной организации процесса, поиска и разработки методов решений поставленной задачи. В данной задаче исследование операций осуществляю я.
Существуют ограничения на количество ресурсов и выпускаемых изделий:
Доски I типа, доски II типа, трудовой ресурс, установленное условие количества изделий. Данные ограничения приведены в системе:
x1 + x2 + 12x3 + 15x4≤1500 - доски I типа.
x1 + 2x2 + 6x3 + 5x4≤1000 - доски II типа.
7x1 + 5x2 + 10x3 + 12x4≤3200 - трудовой ресурс.
x1≥40 - количество столов.2≥120 - количество стульев.3≥20 - количество шкафов платяных.4≤20 - количество шкафов книжных.
Критерий эффективности
Цель задачи: Определить, какое количество изделий, выпускаемых фабрикой, удовлетворяющих последней системе, будет максимизировать прибыль.
Т.к. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно организации операции и параметров, заданных выше, то целевая функция имеет вид: L(x) = 60x1+25x2 +140x3+160x4 (→max)
Стратегии ОС
Стратегиями оперирующей стороны в данной операции называются допустимые способы расходования ею имеющихся активных средств. В виду поставленной цели и имеющихся у меня в настоящий момент знаний, лучшая и выполнимая стратегия - рассчет оптимального количества изделий. ЛПР может перейти к другим стратегиям, путем введения новых ограничений, и активных средств. Так же можно предположить существование субъективных желаний исполнителя и заказчика, определяющее выбор стратегии ОС. Количество этих стратегий определяется многоугольником решений задачи. ЛПР может принять и выбрать любую из них.
2. Методы решения
Данная задача относится к типу целочисленных.
Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования.
При решении полностью целочисленных задач линейного программирования используются:
методы отсечений
методы разветвлений
приближенные методы (даны допустимые решения, хотя и в общем случае неоптимальные)
Небольшая размерность задачи позволяет применить метод динамического программирования и метод сечения Гомори. Т.к. в основе последнего лежит двойственный симплекс метод линейного программирования, позволяющий наряду с нахождением решения, выявить и чувствительность модели к изменению параметров, то решим задачу этим методом.
. Решение задачи
программирование прибыль мебельный таблица
Цель задачи - получение максимальной прибыли - может быть достигнута несколькими способами. Математическим выражением цели является критериальная функции L, структура которой отражает вклад каждого из способов достижения цели. В сформулированной задаче представлено n таких способов. Под способом достижения цели понимается получение информации о распределении ресурсов для максимизации прибыли. Коэффициент Cj представляет собой удельную прибыль применения j-того способа достижения цели (прибыль от продажи одного изделия j-того типа). Переменные Хj - искомые величины, представляющие собой интенсивность использования j-того способа достижения цели (количество изделий j-того типа).
Для достижения цели имеем: m- виды ресурсов, bi - возможный объем потребления i-того ресурса (максимальное количество древесного ресурса и трудового фактора). Коэффициент aij - расход i-того ресурса для производства одного изделия j-того типа.
Метод Гомори
Решим задачу с нецелочисленными переменными:
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
5x1 + x2 + 12x3 + 15x4≤1500
x1 + 2x2 + 6x3 + 5x4≤1000
7x1 + 5x2 + 10x3 + 12x4≤3200
x1≥40
x2≥1203≥204≤20
хi≥0
Этап 1
Приведем модель к стандартному виду: введем балансовые переменные x5, x6, x7, x8, x9, x10, x11, не имеющие физического смысла для приведения неравенств к равенствам.
Максимизировать
L(x) = 60x1+25x2 +140x3+160x4
при ограничениях
x1 + x2 + 12x3 + 15x4 + x5 = 1500
3x1 + 2x2 + 6x3 + 5x4 + x6 = 1000
x1 + 5x2 + 10x3 + 12x4+x7 = 3200
x1 -x8 = 40
x2 -x9 = 1203-x10 = 20
x4 +x11 = 201… x11≥0
Решение системы производится путём ввода искусственных переменных Хi. Для исключения из базиса этих переменных, их вводят в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл "штрафов" за ввод искусственных переменных. Таким образом, из исходной получается новая M-задача.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна - для составляющей L(x), а другая - для составляющей M. При составлении симплекс таблицы полагают, что исходные переменные являются небазисными, а дополнительные (xn+m) и искусственные(Xi)- базисными.
Этап 2
Введем искусственные переменные x12, x13, x14
x1 + x2 + 12x3 + 15x4 + x5 = 1500
x1 + 2x2 + 6x3 + 5x4+x6 = 1000
x1 + 5x2 + 10x3 + 12x4 +x7 = 3200
x1 -x8 +x12 = 40
x2 -x9 + x13