Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Моделирование и решение задач целочисленного программирования.
Цель работы: закрепить навыки построения математических моделей задач принятия решений и освоить методы решения задач целочисленного программирования на контрольных примерах.
Порядок выполнения работы:
1.Сформулировать математическую модель
2.Решить задачу с использованием пакета прикладных программ
3.Дать анализ результатов
4.Подготовиться к защите по нижеприведенным контрольным вопросам.
Контрольные вопросы.
Варианты заданий
Задача 1.
Стальные прутья длиной 110 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 шт. Возможные варианты разреза и величина отходов при каждом из них приведены в следующей таблице:
|
Длина заготовки (см) |
Вариант разреза |
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
45 35 50 |
2 - - |
1 1 - |
1 - 1 |
- 3 - |
- 1 1 |
- - 2 |
|
Величина отходов (см) |
20 |
30 |
15 |
5 |
25 |
10 |
Определить, сколько прутьев по каждому из возможных вариантов следует разрезать, чтобы обеспечить нужное количество заготовок каждого вида при минимальных отходах.
Как изменится модель и решение задачи, если из заготовок выпускаются комплекты: 2 заготовки по 45 см., 3 заготовки по 35 см., 1 заготовка по 50 см.
Максимизируется число комплектов. Число прутьев, которое имеется, взять из решения первоначальной задачи. Как при этом изменятся отходы?
Задача 2.
Для выполнения работ могут быть использованы n механизмов. Производительность i-го механизма (i=1,n) при выполнении j-ой работы (j=1,n) равна cij. Предполагая, что каждый механизм может быть использован только на одной работе и каждая работа может выполняться только одним механизмом, определить закрепление механизмов за работами, обеспечивающее максимальную производительность.
Построить математическую модель задачи.
Как изменится модель и решение, если имеется 2 механизма 1-го типа, 3 механизма 2-го типа, 1 механизм 3-го типа и 2 механизма 4-го типа и при этом на объекте не может находиться более 7 механизмов.
Задача 3.
Министерству необходимо составить план развития каждого из m предприятий, выпускающих однородную продукцию. Число возможных вариантов развития i-го предприятия различно и равно ni. Реализация j-го варианта развития i-го предприятия (j=1,n) требует капитальных затрат, равных Kij, и обеспечивает выпуск продукции в объеме bij единиц. При этом экономический эффект от капитальных вложений на развитие i-го предприятия по j-му варианту равен cij. Учитывая, что необходимо выпустить продукции в количестве B единиц и что общая величина капиталовложений ограничена и равна K, составить такой план развития предприятий, при котором экономический эффект от реализации выбранных вариантов развития предприятий является максимальным.
K=10 B=40
млн. руб.
Как изменится решение, если К и В уменьшатся на 20 %.
Задача 4.
В аэропорту для перевозки пассажиров по n маршрутам может быть использовано m типов самолётов. Вместимость самолёта i-го типа равна ai человек, а количество пассажиров, перевозимых по j-му маршруту за сезон, составляет bi человек. Затраты, связанные с использованием самолёта i-го типа на j-ом маршруте, составляет cij руб.
Определить, сколько самолётов данного типа и на каком из маршрутов следует использовать, чтобы удовлетворить потребности в перевозках при наименьших общих затратах.
a1=100 a2=150 a3=200
b1=10т b2=20т b3=8т b4=30т
Подсчитать количество самолетов каждого типа в оптимальном решении. Как изменится решение, если самолетов 2-го типа есть только 100, а 3-го типа меньше 100.
Задача 5.
В обувном производственном объединении производится раскрой m различных партий материалов, причём каждая из партий состоит из bi единиц материала, имеющего одинаковую форму (например, пластины) и размер. Из материалов всех партий требуется выкроить максимальное количество комплектов деталей обуви, в каждый из которых входит dj (j=1,n) деталей j-того вида, если при раскрое единицы материала i-ой партии по k-му варианту (k=1,K) получается aikj деталей j-го вида.
b1=100 b2=200
d1=2 d2=1
a111=2 a112=4 a121=3 a122=1
a211=4 a212=7 a221=5 a222=6
Задача 6.
Для выполнения четырёх видов землеройных работ могут быть использованы экскаваторы четырёх типов. Производительность экскаватора i-го типа при выполнении j-ой работы задаётся матрицей
Учитывая, что на каждой из работ может быть занят только лишь один экскаватор и что все экскаваторы должны быть задействованы, найти такое распределение экскаваторов между работами, которое обеспечивает максимальную производительность. Как изменится модель и решение, если имеется 2 экскаватора 1-го типа, 3 экскаватора 2-го типа, 1 экскаватор 3-го типа, 2 экскаватора 4-го типа, а общее число экскаваторов не может превышать 6?
Задача 7.
Пароход может быть использован для перевозки 11 наименований груза, масса, объём и цена единицы каждого из которых приведены в следующей таблице:
|
Параметры единицы груза |
Номер груза |
||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
|
Масса (т) Объём (м3) Цена (тыс. Руб.) |
80 100 4,4 |
62 90 2,7 |
92 96 3,2 |
82 110 2,8 |
90 120 2,7 |
60 80 2,8 |
81 114 3,3 |
83 60 3,5 |
86 106 4,7 |
65 114 3,9 |
83 86 4,0 |
На пароход может быть погружено не более 800 т груза общим объёмом, не превышающим 600 м3. Определить, сколько единиц каждого груза следует поместить на пароход так, чтобы общая стоимость размещённого груза была максимальной. Как изменится решение, если количество единиц каждого груза ограничено величинами соответственно: 2;1;4;2;2;3;4;4;4;3;3?
Задача 8.
Из листового проката нужно выкроить заготовки четырёх видов. Один лист длиной 184 см можно разрезать на заготовки длиной 45, 50, 65 и 85 см. Всего заготовок каждого вида необходимо соответственно 90, 96, 88 и 56 шт. Способы разреза одного листа на заготовки и величина отходов при каждом способе приведены в следующей таблице:
|
Длина заготовки (см) |
Количество заготовок, выкраиваемых из одного листа при разрезе определенным способом |
||||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
|
45 50 65 85 |
4 - - - |
2 1 - - |
2 - 1 - |
2 - - 1 |
1 2 - - |
1 - 2 - |
1 1 1 - |
1 1 - 1 |
- 3 - - |
- 2 1 - |
- 1 2 - |
- - 1 1 |
- 2 - - |
|
Величина отходов (см) |
4 |
44 |
29 |
9 |
39 |
9 |
24 |
4 |
34 |
19 |
4 |
34 |
14 |
Определить, какое количество листов по каждому из способов следует разрезать, чтобы получить нужное количество заготовок данного вида при минимальных общих отходах.
Как изменится модель и решение, если в окончательное изделие (комплект) входит 2 заготовки 1-го и 2-го вида и 3 заготовки 3-го и 4-го вида. Максимизируется число комплектов. Изменятся ли отходы для такого оптимального решения? (Общее число листов взять из результатов 1-й постановки задачи)
Задача 9.
Имеются одинаковые заготовки, которые могут быть раскроены тремя способами. Из имеющихся заготовок нужно получить не менее 10 деталей 1-го типоразмера, не менее 8-ми деталей 2-го типоразмера и не менее 10-ти деталей 3-го типоразмера. Способы раскроя определяются матрицей вида:
Здесь aij – количество деталей типоразмера i, получаемое из одной заготовки путём её раскроя способом j.
Количество заготовок, раскраиваемых каждым способом, должно быть целым и не превышать 4-х. Отходы от раскроя одной заготовки для каждого из способов составляют 4, 5 и 5 (усл. единиц). Предложить вариант раскроя с минимальными суммарными отходами. Определить величину этих отходов.
Фирма предполагает продавать выкроенные детали по ценам $4, $6 и $2,5 соответственно для 1-го, 2-го и 3-го типоразмера. При этом потери от процедуры раскроя оцениваются величиной $0,3 на условную единицу отходов. Оптимизируйте процесс раскроя, исходя из соображений получения максимальной прибыли.
Задача 10.
Рассматриваются пять проектов, которые могут быть осуществлены в течение последующих трёх лет. Ожидаемые величины прибыли от реализации каждого из проектов и распределение необходимых капиталовложений по годам (в тыс. долларов) приведены в таблице.
Проект |
Распределение капиталовложений |
Прибыль |
||
Год 1 |
Год 2 |
Год 3 |
||
|
1 |
5 |
1 |
8 |
20 |
|
2 |
4 |
7 |
10 |
40 |
|
3 |
3 |
9 |
2 |
20 |
|
4 |
7 |
4 |
10 |
15 |
|
5 |
8 |
6 |
1 |
30 |
|
Максимальный объем капиталовложений |
25 |
25 |
25 |
Предполагается, что каждый утверждённый проект будет реализован за трёхлетний период.
Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли.Как изменится максимум суммарной прибыли, если максимальный объем капиталовложений уменьшать от 25 до 0, или увеличивать от 25 до бесконечности? Построить график.
Задача 11.
Руководство завода предполагает провести комплекс организационно-технических мероприятий по модернизации производства. Перечень возможных мероприятий приведён в таблице. На реализацию всех мероприятий завод может выделить:
|
Мероприятие |
Трудовые ресурсы (чел. дни) |
Финансовые ресурсы (млн. руб.) |
Производственные площади (кв. м) |
Экономический эффект (млн. руб.) |
|
Закупка станков с ЧПУ |
350 |
400 |
130 |
13000 |
|
Текущий ремонт |
250 |
90 |
- |
3000 |
|
Монтаж транспортного конвейера |
100 |
60 |
300 |
8000 |
|
Установка рельсового крана |
200 |
300 |
150 |
12000 |
|
Ввод системы контроля качества |
130 |
- |
150 |
2500 |
|
Разработка АСУ |
800 |
500 |
100 |
15000 |
Какие мероприятия следует провести, располагая этими ресурсами, чтобы общий экономический эффект был максимальным? Какова величина этого эффекта? Какой объём выделяемых ресурсов останется неиспользованным при реализации найденного варианта? Изменится ли решение задачи, если завод выделит на модернизацию 1 млрд. руб.?
Изменится ли решение задачи, если завод полностью удовлетворит потребности модернизации в производственных площадях и трудовых ресурсах при прежнем финансировании?
Задача 12.
В регионе работают 4 химических завода. Им предложено принять участие в конкурсе по размещению госзаказа на производство изделий 5-ти наименований в объёмах, приведённых в таблице.
|
Наименование изделия |
|||||
|
Объём заказа (шт.) |
A1 |
A2 |
A3 |
A4 |
A5 |
|
350 |
250 |
400 |
150 |
150 |
Каждый из заводов представил несколько вариантов годовой производственной программы по выполнению госзаказа и соответствующие финансовые условия. Программа включает выпуск всех изделий.
|
Варианты завода 1 |
Варианты завода 2 |
Варианты завода 3 |
Варианты завода 4 |
|||||||
|
Наименование изделия |
1 |
2 |
3 |
1 |
2 |
1 |
2 |
3 |
1 |
2 |
|
A1 |
100 |
200 |
200 |
50 |
80 |
- |
- |
100 |
100 |
50 |
|
A2 |
200 |
100 |
150 |
- |
- |
200 |
250 |
100 |
40 |
60 |
|
A3 |
300 |
250 |
200 |
120 |
100 |
100 |
50 |
500 |
60 |
100 |
|
A4 |
100 |
50 |
100 |
100 |
50 |
- |
- |
- |
50 |
- |
|
A5 |
50 |
100 |
80 |
- |
- |
100 |
100 |
80 |
150 |
100 |
|
Объём финансирования (млрд. руб.) |
12 |
16 |
14 |
7 |
9 |
16 |
15 |
17 |
5 |
8 |
Каковы минимальные затраты на выполнение госзаказа?
Какой вариант размещения заказа обеспечивает его выполнение при минимальных объёмах финансирования?
Как изменится решение, если учесть, что заводы 1 и 4 не могут одновременно выполнять однотипные варианты размещения заказов?
Задача 13.
Нефтеперерабатывающее предприятие использует в производстве нефть трёх сортов (1, 2 и 3). Резервные запасы нефти каждого сорта должны быть не меньше соответственно 20, 40 и 60 тыс. тонн. Для хранения нефти могут быть использованы 4 резервуара ёмкостью 25, 30, 35 и 40 тыс. тонн. Затраты на хранение 1-ой тонны нефти сорта 2 на 10% выше, чем сорта 1, а сорта 3 – на 20% выше, чем сорта 1. Смешение нефти разных сортов при хранении не допускается.Резервуары заполняются полностью.
Сколько резервуаров следует использовать?
Как распределяются сорта нефти по резервуарам?
Каковы минимальные затраты на хранение нефти?
Целесообразно ли устанавливать дополнительный резервуар объёмом 20 тыс. тонн?
Задача 14.
Для реконструкции машиностроительного предприятия было представлено на выбор 10 проектов, каждый из которых характеризуется четырьмя агрегированными показателями и ежегодной ожидаемой прибылью, представленными в таблице.
|
Агрегированный показатель проекта |
Варианты проектов |
|||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
Затраты труда (нормо-час) |
50 |
60 |
30 |
40 |
80 |
70 |
50 |
20 |
40 |
50 |
|
Затраты энергии (тыс. квт) |
4 |
4 |
2 |
5 |
5 |
2 |
3 |
6 |
6 |
3 |
|
Расходы на материалы (млн. руб.) |
3 |
2 |
4 |
5 |
3 |
2 |
4 |
2 |
2 |
3 |
|
Финансовые средства (млн. руб.) |
7 |
5 |
9 |
6 |
4 |
3 |
7 |
2 |
4 |
5 |
|
Ожидаемая прибыль (млн. руб.) |
9 |
8 |
8.5 |
8.8 |
9 |
8 |
9 |
8.7 |
8.9 |
8 |
При выборе проектов необходимо учесть ряд ограничений технологического характера:
Выбрать проекты для реконструкции предприятия, обеспечивающие максимальную ожидаемую прибыль. Каков размер этой прибыли?
Задача 15.
Объединение кабельной промышленности состоит из 3-х заводов. Номенклатура выпускаемых изделий включает три позиции: “кабель силовой”, “провод для осветительных установок”, “провод обмоточный”. При планировании развития объединения на три года разработаны три варианта (1-3) для завода 1, 2 варианта (4-5) для завода 2 и один (6) – для завода 3.
(В таблице все данные в условных единицах)
Требуется выбрать варианты для включения в план развития объединения, обеспечивающие удовлетворение заданной потребности в кабельных изделиях и реализуемые с минимальными затратами. Каковы эти затраты?
|
Вариант |
Производство кабельных изделий по годам |
ЗЗатраты за 3 года |
||||||||
|
Кабель |
Провод силовой |
Провод обмоточный |
||||||||
|
1 |
2 |
3 |
1 |
2 |
3 |
1 |
2 |
3 |
||
|
1 2 3 4 5 6 |
6.9 7 7 19 16 - |
8 7 7.8 23 18 - |
10 8.6 8.7 28 22 - |
37 25 30 - - - |
44 - - - - 864 |
53 - - - - 950 |
2.8 3 6 13 16 - |
3 18 18 15 18 - |
4 20 20 18 21 - |
1557 1399 1034 2822 3044 364 |
|
Потребность |
15 |
17 |
25 |
20 |
300 |
450 |
10 |
15 |
10 |