Программирование и основы алгоритмизации (ведение в исследование операций)

Обеспечение наибольшей прибыли от реализации выпускаемой продукции мебельной фабрики. Решение задачи в среде MS Excel. Выполнение преобразования симплексной таблицы методом Жордана-Гаусса. Применение метода динамического программирования и сечения Гомори.
Краткое сожержание материала:

Размещено на

Размещено на

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

по дисциплине «Программирование и основы алгоритмизации (введение в исследование операций)»

Содержание

Введение

1. Формализация задач

2. Методы решения

3. Решение задачи

4. Решение задачи в среде MS EXCEL

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

Заключение

Литература

Введение

Мебельная фабрика выпускает столы, стулья, платяные и книжные шкафы. При изготовлении этой продукции используется два типа древесных материалов (досок). В таблице приведены нормативные затраты на единицу изделия. Объемы наличных ресурсов каждого типа соответственно равны 1500, 1000, 3200. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно.

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

Таблица 1

Ресурсы	Запас ресурсов	Затраты
		Стол	Стул	Шкаф платяной	Шкаф книжный
Доски I типа	1500	5	1	12	15
Доски II типа	1000	3	2	6	5
Труд чел./ч.	3200	7	5	10	12
Прибыль		60	25	140	160

1. Формализация задачи

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

Организация операции.

В качестве параметров, описывающих количество каждого вида продукции, примем:

x₁ - количество столов, x₂ - количество стульев, x₃ - количество шкафов платяных, x₄ - количество шкафов книжных. Единица измерения - штуки. При этом, имеем условные ограничения: количество выпускаемой продукции не может быть отрицательным, и является целым числом: хi?0, хi-целые числа (i = 1…4).

Оперирующая сторона

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

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

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

Существуют ограничения на количество ресурсов и выпускаемых изделий:

Доски I типа, доски II типа, трудовой ресурс, установленное условие количества изделий. Данные ограничения приведены в системе:

5x₁ + x₂ + 12x₃ + 15x₄?1500 - доски I типа.

3x₁ + 2x₂ + 6x₃ + 5x₄?1000 - доски II типа.

7x₁ + 5x₂ + 10x₃ + 12x₄?3200 - трудовой ресурс.

x₁?40 - количество столов.

x₂?120 - количество стульев.

x₃?20 - количество шкафов платяных.

x₄?20 - количество шкафов книжных.

Критерий эффективности

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

Т.к. Прибыль от реализации единицы изделия - 60, 25, 140 и 160 р. соответственно организации операции и параметров, заданных выше, то целевая функция имеет вид: L(x) = 60x₁+25x₂ +140x₃+160x₄ (>max)

Стратегии ОС

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

2. Методы решения

Данная задача относится к типу целочисленных.

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

При решении полностью целочисленных задач линейного программирования используются:

- методы отсечений

- методы разветвлений

- приближенные методы (даны допустимые решения, хотя и в общем случае неоптимальные)

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

3. Решение задачи

программирование прибыль мебельный таблица

Цель задачи - получение максимальной прибыли - может быть достигнута несколькими способами. Математическим выражением цели является критериальная функции L, структура которой отражает вклад каждого из способов достижения цели. В сформулированной задаче представлено n таких способов. Под способом достижения цели понимается получение информации о распределении ресурсов для максимизации прибыли. Коэффициент C_j представляет собой удельную прибыль применения j-того способа достижения цели (прибыль от продажи одного изделия j-того типа). Переменные Х_j - искомые величины, представляющие собой интенсивность использования j-того способа достижения цели (количество изделий j-того типа).

Для достижения цели имеем: m- виды ресурсов, b_i - возможный объем потребления i-того ресурса (максимальное количество древесного ресурса и трудового фактора). Коэффициент a_ij - расход i-того ресурса для производства одного изделия j-того типа.

Метод Гомори

Решим задачу с нецелочисленными переменными:

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

L(x) = 60x₁+25x₂ +140x₃+160x₄

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

5x₁ + x₂ + 12x₃ + 15x₄?1500

3x₁ + 2x₂ + 6x₃ + 5x₄?1000

7x₁ + 5x₂ + 10x₃ + 12x₄?3200

x₁?40

x₂?120

x₃?20

x₄?20

хi?0

Этап 1

Приведем модель к стандартному виду: введем балансовые переменные x₅, x₆, x₇, x₈, x₉, x_10, x_11, не имеющие физического смысла для приведения неравенств к равенствам.

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

L(x) = 60x₁+25x₂ +140x₃+160x₄

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

5x₁ + x₂ + 12x₃ + 15x₄ + x₅ = 1500

3x₁ + 2x₂ + 6x₃ + 5x₄ + x₆ = 1000

7x₁ + 5x₂ + 10x₃ + 12x₄+x₇ = 3200

x₁ -x₈