Лабораторная работа 5 Тема- Моделирование и решение задач целочисленного программирования

Работа добавлена на сайт samzan.net:

Лабораторная работа № 5 

Тема: Моделирование и решение задач целочисленного  программирования.

Цель работы: закрепить навыки построения математических моделей задач принятия решений и освоить методы решения задач целочисленного  программирования на контрольных примерах.

Порядок выполнения работы:

1.Сформулировать математическую модель

2.Решить задачу с использованием пакета прикладных программ

3.Дать анализ результатов

4.Подготовиться к защите по нижеприведенным контрольным вопросам.

Контрольные вопросы.

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.

Руководство завода предполагает провести комплекс организационно-технических мероприятий по модернизации производства. Перечень возможных мероприятий приведён в таблице.   На реализацию всех мероприятий завод может выделить:

1.  трудовых ресурсов – 1300 чел-дней,
2.  финансовых ресурсов – 800 млн. руб.
3.  производственных площадей –700 кв. м

Мероприятие	Трудовые ресурсы   (чел. дни)	Финансовые ресурсы (млн. руб.)	Производственные площади             (кв. м)	Экономический эффект          (млн. руб.)
Закупка станков с ЧПУ	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

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

1.  одновременно может быть реализовано не более семи проектов
2.  5-ый и 8-ой проекты взаимно исключают друг друга
3.  1-ый проект может быть реализован лишь при условии реализации второго
4.  4-ый проект может быть реализован лишь при условии реализации хотя бы одного из двух проектов: либо 3-его, либо 10-ого.

Выбрать проекты для реконструкции предприятия, обеспечивающие максимальную ожидаемую прибыль. Каков размер этой прибыли?

 Задача 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

1. Введение В реформировании российской экономики еще со времен перестройки коммерческие организации взяли
2. Балтийский федеральный университет имени Иммануила Канта БФУ им.
3. Предложить пациенту лечь в удобное для него положение
4. а вылившийся в гражданскую войну а также религиозная война между англиканами и пуританами
5. .01.14 9 тур 18.
6. ЭЛИТ КЕРАМИКА молодая и амбициозная компания осуществляет более 3х лет поставки керамического гранита
7. 0.006 0.html
8. вариантам Фамилии студентов начинающиеся на буквы А до Д выполняют-
9. Построение чертежа детали с использованием системы автоматизированного проектирования общего назначения Автокад
10. Денежное обращение и денежная система
11. РЕФЕРАТ дисертації на здобуття наукового ступеня кандидата сільськогосподарських наук1
12. на тему
13. Клиническая психология
14. Задание 11 Проверка независимости момента сил трения от угловой скорости вращения блока
15. ных условиях строительства- в крупных городах и в ненаселённой местности; зимой и в жарком климате; в сложных
16. морское училище имени М
17. вступает в конфликты не одалживает и не берет в долг
18. Невский проспект
19. Л.Д. Троцкий- жизнь в революции
20. Разработка конструкции мобильной ленточной пилорамы

Материалы собраны группой SamZan и находятся в свободном доступе