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

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

Содержание Введение

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

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

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

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

5. Анализ задачи на чувствительность Заключение Литература

Введение

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

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

Таблица 1

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₈ = 40

x₂ -x₉ = 120

x₃-x₁₀ = 20

x₄ +x₁₁ = 20

x_1… x₁₁?0

Решение системы производится путём ввода искусственных переменных Х_i. Для исключения из базиса этих переменных, их вводят в целевую функцию с большими отрицательными коэффициентами M, имеющими смысл «штрафов» за ввод искусственных переменных. Таким образом, из исходной получается новая M-задача.

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

Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна — для составляющей L (x), а другая — для составляющей M. При составлении симплекс таблицы полагают, что исходные переменные являются небазисными, а дополнительные (x_n+m) и искусственные (X_i) — базисными.

Этап 2

Введем искусственные переменные x₁₂, x₁₃, x₁₄

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

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

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

x₁ -x₈ +x₁₂ = 40

x₂ -x₉ + x₁₃ = 120

x₃ -x₁₀ + x₁₄ = 20

x₄ +x₁₁ = 20

Целевая функция:

L (X) = 60x₁+25x₂+140x₃+160x₄ — Mx₁₂ — Mx₁₃ — Mx₁₄ > max

Из уравнений выражаем искусственные переменные:

x₁₂ = 40-x₁+x₈

x₁₃ = 120-x₂+x₉

x₁₄ = 20-x₃+x₁₀

подставим в целевую функцию:

L (X) = (60+M)x₁+(25+M)x₂+(140+M)x₃+(160)x₄+(-M)x₈+(-M)x₉+(-M)x₁₀+

+(-180M) x₁₁

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

1. Размерность матрицы, А — m x n, m=7, n=14.

2. Матрица А:

Таблица 2

3. Вектор свободных членов в уравнениях ограничений b_i, i=1…m:

b=(1500, 1000, 3200, 40, 120, 20, 20)

4. Коэффициенты при переменных в критериальной функции C_j:

C=(60+M, 25+M, 140+M, 160,0,0,0,-M,-M,-M, -180M, 0,0,0)

Этап 4

Симплекс преобразования.

Решим систему уравнений относительно базисных переменных:

x₅, x₆, x₇, x₁₂, x₁₃, x₁₄, x₁₁,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,1500,1000,3200,0,0,0,20,40,120,20)

Таблица 3

Итерация № 0.

Первый опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

b_i / a_i3 и из них выберем наименьшее: x₁₄ — разрешающая строка

Разрешающий элемент = 1.

Таблица 4

Таблица 5. Получаем новую симплекс-таблицу:

Итерация № 1.

Данный опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее: строка x₁₂

Разрешающий элемент = 1

Таблица 6

Таблица 7. Получаем новую симплекс-таблицу:

Итерация № 2.

Текущий план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i2 и из них выберем наименьшее: x₁₃ строка является разрешающей.

Разрешающий элемент =1

Таблица 8

Таблица 9. Получаем новую симплекс-таблицу:

Итерация № 3.

Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее: строка x₁₁

Разрешающий элемент =1.

Таблица 10

Получаем новую симплекс-таблицу:

Таблица 11

Итерация № 4.

Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

В качестве разрешающего выберем столбец x₁₀, так как это наибольший коэффициент по модулю.

Вычислим значения? по строкам как частное от деления: b_i / a_i10 и из них выберем наименьшее: строка x₅ разрешающая.

Разрешающий элемент =12.

Таблица 12

Получаем новую симплекс-таблицу:

Таблица 13

Итерация № 5.

Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i11 и из них выберем наименьшее: x₄ разрешающая строка.

Разрешающий элемент = 1.

Таблица 14

Получаем новую симплекс-таблицу:

Таблица 15

Итерация № 6.

Текущий опорный план неоптимален, т.к. нарушены условия оптимальности: критериальная функция имеет отрицательные коэффициенты.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i9 и из них выберем наименьшее: строка x₆ разрешающая.

Разрешающий элемент равен =1¹/₂

Таблица 16

Получаем новую симплекс-таблицу:

Таблица 17

Итерация № 7.

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

Вычислим значения? по строкам как частное от деления: b_i / a_i4 и из них выберем наименьшее: строка x₁₁ разрешающая.

Разрешающий элемент равен =1.

Таблица 18

Получаем новую симплекс-таблицу:

Таблица 19

Индексная строка не содержит отрицательных элементов — найден оптимальный план Окончательный вариант симплекс-таблицы:

Таблица 20

Оптимальный план можно записать так:

x₁₀ = 47⁷/₉

x₉ = 66²/₃

x₇ = 1068⁸/₉

x₁ = 40

x₂ = 186²/₃

x₃ = 67⁷/₉

x₄ = 20

F (X) = 60*40 + 25*186²/₃ + 140*67⁷/₉ + 160*20 = 19 755⁵/₉

Этап 5

В полученном оптимальном плане присутствуют дробные числа.

По 3-у уравнению с переменной x₇, получившей нецелочисленное значение в оптимальном плане с наибольшей дробной частью ⁸/₉, составляем дополнительное ограничение:

⁸/₉-⁵/₉x₅-²/₉x₆-⁴/₉x₈-⁵/₉x₁₁?0

Преобразуем полученное неравенство в уравнение:

⁸/₉-⁵/₉x₅-²/₉x₆-⁴/₉x₈-⁵/₉x₁₁ + x₁₂ = 0,

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

Поскольку двойственный симплекс-метод используется для поиска минимума целевой функции, делаем преобразование L (x) = -L (X).

Таблица 21

На пересечении ведущих строки и столбца находится разрешающий элемент равный ^-4/₉

Таблица 22

Выполняем преобразования симплексной таблицы методом Жордана-Гаусса.

Таблица 23

Решение получилось целочисленным. Нет необходимости применять метод Гомори.

Оптимальный целочисленный план можно записать так:

x₁₀ = 47

x₉ = 66

x₇ = 1066

x₁ = 42

x₂ = 186

x₃ = 67

x₄ = 20

x₈ = 2

L (X) = 19 750

Решение задачи: стульев нужно произвести 42 шт., столов 186 шт., шкафов платяных 67 шт., шкафов книжных 20 шт. Прибыль при полученном решении составляет 19 750 р. Значения остальных переменных, введенных для преобразования неравенств в равенства, не имеют физического смысла. В ходе решения соблюдены все ограничения.

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

Ручной просчет формулами доказан функцией «Поиск решения» в среде MS EXCEL.

К данному решению прилагаю файл *.xls, с ручным просчетом и решением задачи с помощью стандартной функции MS Excel «Поиск решения».

5. Анализ задачи на чувствительность Произведем анализа задачи на чувствительность в среде MS EXCEL.

Ресурс доски I типа — дефицитный Ресурс доски II типа — дефицитный Ресурс трудовой недефицитный.

Т.к. EXCEL позволяет анализ на устойчивость только нецелочисленной задачи, то ответ запишу приближенно.

Интерпретация: допустимо уменьшение трудового ресурса на 1068 ч/час (с целочисленным округлением), уменьшение количества досок II типа на 100 шт., досок I типа на 430 шт. Так же уменьшения производства мебели каждого типа, кроме книжных шкафов и столов (см. столбец «допустимое уменьшение»). Аналогично допустимое увеличение ресурсов и количества мебели.

При этом оптимальное решение таково:

X₁ = 40, x₂ = 186, x₃ = 67, x₄ = 20. А максимальная прибыль составит около 19 755 р.

Заключение

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

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

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

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

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

Литература

Фаронов В. В. Программирование на персональных ЭВМ. — М.: Изд-во МГТУ, 2009.-580 с.

Фаронов В. В. Алгоритмизация (в 3-х книгах). Кн.1. Основы Турбо Паскаля. — М.: Учебно-инженерный центр <<�МВТУ — ФЕСТО ДИДАКТИК>>, 2010. — 304 с.

Федоров А. Особенности программирования. — Киев.: Диалектика, 2008.-144 с.

Хершель Р. Программирование. /2-е изд., перераб. — Вологда: МП <<�МИК>>, 2009.-342 с.

Форонов В. В. Алгоритм. Начальный курс. Учебное пособие. Издание 7-е, переработанное. М.: <<�Нолидж>>, издатель МОЛГАЧЕВА с.в., 2009. — 576 с.

Пильщиков В. Н. Сборник упражнений Учеб. пособ. для вузов. — М.: Наука, 2006.