Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

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

Работа добавлена на сайт samzan.ru: 2016-03-13


Лабораторная работа № 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. Фонтан С Новым 2014 Годом
3. Земли Человека Вселенной необходимы для каждого человека идущего путем развития расширения своего созн
4. Зарубежный опыт ипотечного жилищного кредитования и его использование в России
5. 1учитывает деятельность всех участников производства сферы услуг и материальных благ; 2содержит показат
6. ещё можно добавить в этот долгий список
7. Йорке в 1964 году проходила Всемирная выставка известный писательфантаст и профессор биохимии Бостонского у
8. Поскреби русского и найдешь татарина
9. Шимпанзе в храме языка
10. УТВЕРЖДАЮ Ректор университета А
11. тема квалифицирующих признаков преступлений против общих правил безопасности по сравнению с УК 1960 годом под
12. Облік і аудит Тернопіль ТНЕУ ~ 2013 ЗМІСТ
13. Многие искусствоведы относят его к весьма отдаленным эпохам- говорят о Р
14.  Абсцесс перегородки носа
15. Доходы бюджет
16. Первый закон Ньютона
17. Подготовительный этап 1.html
18. Анализ деятельности предприятия
19. dvertising
20. Областной центр занятости (подразделения в 5 городах области)