Математическое программирование. Методы оптимизации

Задания для самостоятельного выполнения Методические указания


При выполнении задания 1 можно использовать инструментарий MS Excel. При выполнении заданий 2 и 3 инструментарий MS Excel можно использовать для решения подзадач ЛП на каждой итерации метода ветвей и границ (но не для получения решения в готовом виде).


Задание 1.1.
Руководство предприятия, выпускающего неоднородную продукцию, стремится определить, какими должны быть уровни производства для каждого продукта в течение некоторого наперед заданного периода. Предприятие имеет возможность реализовать от одного до четырех различных типов производственно-технологических процессов и обладает правом выбора того или иного варианта.
Технологические процессы (ТП) первого и второго типов ориентированы на получение продукции А, а технологические процессы третьего и четвертого типов – на получение продукции В. Расходы, связанные с каждым из технологических процессов, определяются трудозатратами (измеряемыми в человеко-неделях), количеством (в единицах веса) потребляемого в течение недели материала М1 и количеством (в ящиках) потребляемого в течение недели материала М2. Т. к. затраты, связанные с различными технологическими процессами, не одинаковы, то прибыльность процессов оказывается разной даже в том случае, когда они используются для получения продукции одного и того же вида.
При составлении производственного плана на неделю диапазон возможностей предприятия ограничен как за счет людских ресурсов, так и за счет потребляемого сырья (материалов М1 и М2). Производственно-экономические показатели и имеющиеся ограничения приведены в таблице 1.5.
Необходимо определить, какими должны быть уровни производства для каждого технологического процесса в течение недели, чтобы обеспечить максимальный суммарный доход.
1. Сформулировать задачу линейного программирования.
2. Найти оптимальный производственный план.

Таблица 1.5


Количество

На единицу продукции А

На единицу продукции В

В наличии (не более)

ТП1

ТП2

ТП3

ТП4

Человеко-недель

1

1

1

1

15

Материала М1 (кг.)

7

5

3

2

120

Материала М2 (ящ.)

3

5

10

15

100

Доход с единицы продукции

4

5

9

11

 

3. Сформулировать двойственную задачу и получить ее оптимальное решение (не решая «с нуля», а используя найденное решение исходной задачи). Дать экономическую интерпретацию двойственной задачи и ее оптимального решения.
4. Выполнить анализ чувствительности найденного оптимального решения, в ходе которого получить ответы на следующие вопросы:
1) В каких пределах может изменяться величина дохода, получаемого с единицы каждого вида продукции, чтобы найденное решение оставалось оптимальным?
2) Какие из ресурсов, используемых для производства, являются в заданных условиях лимитирующими, а какие – нелимитирующими? Как можно использовать эту информацию при решении задачи оптимальной организации производства?
3) Имеются ли среди четырех возможных технологических процессов такие, реализация которых в заданных условиях является экономически невыгодной? Если да, то насколько должен быть увеличен доход от реализации единицы продукции соответствующего типа, чтобы эти процессы вошли в оптимальный план (стали экономически выгодными)?
4) Предположим, что уровень доступности материала М1 увеличился до 130 кг в неделю. Приведет ли это к увеличению суммарного дохода от реализации продукции? Если да, то насколько увеличится доход? Может ли в этом случае измениться структура оптимального плана (какой-либо производственный процесс, который первоначально был признан экономически невыгодным, войдет в оптимальный план, или, наоборот, какой-либо процесс будет исключен из оптимального плана)?
5) Предположим, что уровень доступности материала М2 увеличился до 120 ящ. в неделю. Приведет ли это к увеличению суммарного дохода от реализации продукции? Если да, то насколько увеличится доход? Может ли в этом случае измениться структура оптимального плана? Изменятся ли ответы на эти вопросы, если предположить, что уровень доступности материала М2 увеличился до 170 ящ. в неделю?
6) Предположим, что предприятие имеет возможность высвободить денежные средства, связанные в излишних запасах нелимитирующих ресурсов, и за счет этих средств увеличить уровни доступности лимитирующих ресурсов. Предположим для определенности, что этих средств достаточно для увеличения на 4 единицы запасов любого вида лимитирующих ресурсов. Вложение в какой вид ресурса приведет к наибольшему увеличению дохода?
Оформить отчет. Содержание отчета:
а) Постановка задачи линейного программирования.
б) Полученное оптимальное решение и его экономическая интерпретация.
в) Постановка и экономическая интерпретация двойственной задачи. Оптимальное решение двойственной задачи.
г) Ответы на вопросы п. 4 (с обоснованием).

Задание 1.2.
В условиях задания 1.1 имеется дополнительное ограничение: продукция фирмы является неделимой (фактический смысл имеют только целые значения).
1. Сформулировать задачу целочисленного программирования.
2. Решить поставленную задачу с помощью метода ветвей и границ. Построить дерево работы алгоритма.
3. Показать существование зависимости числа итераций алгоритма от выбора переменной ветвления и последовательности решения подзадач ЛП (достаточно рассмотреть две различные стратегии выбора).
4. Оформить отчет. Содержание отчета:
а) Постановка задачи целочисленного программирования.
б) Описание алгоритма решения методом ветвей и границ.
в) Полученное оптимальное решение и его экономическая интерпретация.
г) Дерево работы алгоритма.
д) Результаты исследований п. 3.

Задание 1.3.
Производится планирование предвыборной кампании. Денежные средства, выделяемые на проведение кампании, ограничены и составляют 18000 д. е.
Избирательный округ включает 8 участков. Данные о числе избирателей и денежных средствах, необходимых для проведения мероприятий кампании по каждому участку, приведены в таблице 1.6.
Таблица 1.6


Участок

Число избирателей

Необходимые средства

1

3100

3500

2

2600

2500

3

3500

4000

4

2800

3000

5

2400

2000

6

2700

2800

7

3600

4200

8

3000

3200

Каждый участок может либо использовать все выделенные ему деньги, либо не использовать их совсем.
Необходимо найти оптимальное распределение денежных средств между участками.
1. Сформулировать задачу целочисленного программирования.
2. Показать, что концептуально задача может рассматриваться как задача о загрузке судна, и решить ее методом ветвей и границ. Построить дерево работы алгоритма.
3. Оформить отчет. Содержание отчета:
а) Постановка задачи целочисленного программирования.
б) Обоснование выбора алгоритма решения.
в) Описание алгоритма решения.
г) Полученное оптимальное решение и его интерпретация.
д) Дерево работы алгоритма.

Оформление: Word + Excel

Заказать эту работу: