Теория принятия решений. Целочисленное и дискретное программирование
Начальная страница. Содержание
Введение    Цели и задачи     Методологические основы     Линейное программирование     Нeлинейное программирование     Нeлинейное программирование: Безусловная однопараметрическая оптимизация     Нeлинейное программирование: Безусловная многопараметрическая оптимизация    Нeлинейное программирование: Условная многопараметрическая оптимизация    Целочисленное и дискретное программирование     Динамическое программирование     Принятие решений в условиях неопределенности     Принятие многоцелевых решений     Марковские процессы принятия решений     Литература    



Теоретические разделы

Задания к лабораторно-практическим занятиям

4.1. Постановка задачи целочисленного программирования

4.2. Метод ветвей и границ

4.3. Рекомендации по формулировке и решению ЦП

4.4. Задачи оптимизации раскроя

4.5. Постановка задачи дискретного программирования

4.6. Контрольные вопросы и задания

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Задача решается с использованием пакета EXCEL или LINGO. В отчете отразить постановку задачи, дерево решений а также приложить распечатки созданных программ и тестовых решений.

 


 

 

 

 

 

 

4.1. Постановка задачи целочисленного программирования

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

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

Как уже отмечалось, часто задачу ЦП решают без учета условий целочисленности переменных, а затем округляют полученное решение с избытком или недостатком. Это не гарантирует получение оптимального целочисленного решения задачи. Поэтому для нахождения оптимального решения целочисленных задач применяют специальные методы, в которых учитывается, что число возможных решений любой целочисленной задачи является конечным. Следовательно, можно рассмотреть все возможные сочетания целочисленных переменных и проверить, удовлетворяют ли они ограничениям, и из числа удовлетворяющих ограничениям, выбрать наилучшее с точки зрения целевой функции. Такой метод называют методом полного перебора. Его трудоемкость с ростом числа переменных и расширением области граничных условий значительно возрастает. Поэтому для реальных задач он неприменим.

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


 

 

 

4.2. Метод ветвей и границ

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

1. Решаем сформулированную задачу как задачу ЛП (обозначим ЛП-1), рассматривая все ее переменные как непрерывные. Пусть W1 - оптимальное значение ее целевой функции. Допустим в оптимальном решении ЛП-1 некоторые целочисленные переменные принимают дробные значения. Тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае W1 - верхняя граница оптимального значения W исходной задачи.

В решенном нами примере линейного программирования 2.1 "Оптимизация размещения побочного производства лесничества" верхняя граница соответствует 34 млн. руб. при x1=3.6 и x2=6.4. Очевидно, что переменные x1 (число откармливаемых бычков) и x2 (количество выращиваемых партий быстрорастущих новогодних елей) должны быть целочислены.

2. Производим ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении ЛП-1. Выбор переменной, по котором производим ветвление, осуществляется по ряду правил:

В рассматриваемой целочисленной версии примера 2.1 в качестве переменной, по которой будет вестись ветвление, следует рассматривать x1, т.к. коэффициент стоимости при этой переменной максимален.

3. Пусть ветвление происходит по xi, дробное значение которой в ЛП-1 равно b i. Далее рассматриваются уже две новые задачи ЛП-2 и ЛП-3, которые образуются путем введения двух дополнительных ограничений xiЈ a i , xi і g i, где a i - наибольшее целое, не превосходящее b i, g i - наименьшее целое, большее b i. Допустим, оптимальные значения ЛП-2 и ЛП-3 содержат дробные значения целочисленных переменных и поэтому не являются допустимыми.

Для рассматриваемого примера b 1=3,6, a 1=3, g 1=4.

4. Производим ветвление в вершине 2 или 3, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления осуществляется с помощью специальных правил:

5. Процесс ветвления и решения задач ЛП продолжаем до получения целочисленного решения одной из задач ЛП. Значение W в полученной точке представляет собой нижнюю границу оптимального значения ЦФ исходной задачи ЦП. На этом этапе все вершины (задачи ЛП), для которых оптимальное значение W не превосходит полученной нижней границы ("прозондированные" вершины). Вершина является прозондированной в следующих случаях:

Ветвление происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим W дает оптимальное решение исходной задачи ЦП.

 

 

ЛП-1

W1=34 млн.руб.

x1=3,6 и x2=6,4.

b 1=3.6, a 1=3, g 1=4.

 

 

 

 

 

 

x1Ј a 1

 

x1і g 1

 

 

ЛП-2

W1=32,5 млн.руб.

x1=3, x2=7.

Оптимальное решение

 

 

 

 

 

 

 

x2Ј a 3

ЛП-3

W1=33.3 млн.руб.

x1=4, x2=5,33,

b 3=5,33, a 3=5, g 3=6.

 

 

 

 

 

x2і g 3

 

 

 

 

 

 

 

 

 

 

 

ЛП-4

W1=33,13 млн.руб.

x1=4,125, x2=5,

b 1=4,125, a 1=4, g 1=5.

 

 

 

 

ЛП-5

Допустимое решение отсутствует

 

 

x1Ј a 4

 

x1і g 4

 

 

ЛП-6

W1=32,5 млн.руб.

x1=4, x2=5.

Оптимальное решение

 

 

 

ЛП-7

W1=25 млн.руб.

x1=5, x2=0.

 

 

Процесс ветвления и решения рассматриваемой задачи представлен на рис.4.1. Оптимальное решение - W=32,5 млн. руб.; x1=4; x2=5.

 


 

 

 

 

 

4.3. Рекомендации по формулировке и решению ЦП

  1. Количество целочисленных переменных уменьшать насколько возможно. Например, целочисленные переменные, значения которых должно быть не менее 20, можно рассматривать как непрерывные.
  2. В отличие от общих задач ЛП, добавление новых ограничений особенно включающих целочисленные переменные, обычно уменьшают время решения задач ЦП.
  3. Если нет острой необходимости в нахождении точного оптимального целочисленного решения, отличающегося от непрерывного решения, например, 3%. Тогда реализацию метода ветвей и границ для задачи максимизации можно заканчивать, если отношение разницы между верхней и нижней границ к верхней границы меньше 0,03.

Метод ветвей и границ можно применять для решения задач нелинейного программирования.

 


 

 

4.4. Задачи оптимизации раскроя

В качестве примера рассмотрим задачу раскроя сырья, который производится практически во всех производствах - в раскряжевке, в лесопилении, в мебельном производстве, изготовлении столярно-строительных изделий и т.д. Поэтому экономное расходование сырья является одной из важнейших задач, подлежащих решению при планировании, организации и управлении производственными процессами в лесном комплексе. Эта задача приобретает еще большую актуальность в связи с экологическими проблемами, вопросами охраны окружающей среды.

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

Знакомство с задачами раскроя начнем с линейного раскроя.

Пример 4.1. Из 50 шт. бревен длиной 6,5 м необходимо изготовить наибольшее число комплектов, в состав каждого из которых входит 2 шт. детали длиной 2 м и 3 шт. детали длиной 1,25 м.

Есть два подхода к решению задач раскроя:

  1. Раскрой делает ЭВМ.
  2. Лицо принимающее решение (ЛПР) принимает несколько различных вариантов раскроя, а ЭВМ выбирает лучший из них.

Подход 1. Раскрой делает ЭВМ

Постановка задачи.

  1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможна другая постановка - качестве показателя эффективности взять число заготовок Z, которое необходимо иметь, чтобы получить заданное цисло комплектов.
  2. В качестве управляемых переменных задачи следует взять xA и xB - соответственно, число деталей А и В, получаемых из одной заготовки; каждая в год.

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

W1 = K(r) max;

или

W2 = Z (r) min.

4. Ограничения:

4.1. По длине заготовки, м:

2 xA + 1,25 xB Ј 6,5.

4.2. По комплектности, шт.:

k xA - 2 K і 0;

k xB - 3 K і 0,

где

k - число заготовок.

4.3. Областные ограничения и требования целочисленности:

xA і 0, xB і 0, K і 0 - целые.

При решении задачи в первой постановке (k=50)

на ЭВМ получено: xA=2; xB=2; K=33. Это означает, что если из одной заготовки выкраивать две 2 м детали и две 1,25 м детали, то максимальное количество комплектов будет 33.

Подход 2. ЛПР принимает несколько различных вариантов раскроя, а ЭВМ выбирает лучший из них

Сырье может раскраиваться на заготовки различными способами - вариантами (картами) раскроя, которые сводятся в специальную таблицу. В этой таблице указывают требуемое число заготовок каждого вида и величина отходов для каждого варианта раскроя. Допустим, в нашем примере ЛПР разработал 4 варианта, которые приведены в табл. 2. Отметим, что вариант предложенный ЭВМ в первом подходе присутствует в таблице как одна из альтернатив.

Таблица 4.1.

Длина заготовки, м

 

Варианты раскроя

Число деталей в комплекте

 

1

2

3

4

2

3

2

1

0

2

1,25

0

2

3

5

3

Отходы

0,5

0

0,75

0,25

-

Число

заготовок

x1

x2

x3

x4

-

Постановка задачи.

  1. В качестве показателя эффективности целесообразно взять число комплектов K, которое можно получить из заданного числа заготовок. Возможны другие постановки - взять число заготовок Z, которое необходимо иметь, чтобы получить заданное число комплектов или отходы O.
  2. В качестве управляемых переменных задачи следует взять:

x1 - число заготовок, раскраиваемых по 1 варианту;

x2 - число заготовок, раскраиваемых по 2 варианту;

x3 - число заготовок, раскраиваемых по 3 варианту;

x4 - число заготовок, раскраиваемых по 4 варианту.

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

W1 = K(r) max;

или

W2 = Z (r) min;

или

W3 = O = 0,5 x1 + 0 x2 + 0,75 x3 + 0,25 x4 (r) min.

4. Ограничения:

4.1. По числу деталей, получаемых в результате раскроя по всем вариантам:

x1 + x2 + x3 + x4 = k,

где

k - число заготовок.

4.2. По комплектности, шт.:

3 x1 + 2 x2 + x3 - 2 K і 0;

2 x2 + 3 x3 + 5 x4 - 3 K і 0;

4.3. Областные ограничения и требования целочисленности:

xA і 0, xB і 0, K і 0 - целые.

При решении задачи в первой постановке (k=50)

на ЭВМ получен результат, представленный в табл. 4.2.

Таблица 4.2.

Переменная

Решения

 

1

2

3

4

5

x1

0

0

0

1

0

x2

41

41

42

40

40

x3

0

1

0

1

2

x4

9

8

8

8

8

K

41

41

41

41

41

Из таблицы 4.2 видно, что существует пять равноценных варианта раскроя, которые приводят к получению 41 комплекта из 50 заготовок. Если данный результат сравнить с результатом, полученным по первому подходу (33 комплекта из тех же самых 50 заготовок), то получаем выигрыш в 8 комплектов. Следовательно, для лучшего использования сырья целесообразно использовать сочетание различных вариантов раскроя.

Подход, при котором выбирается из ряда разработанных ЛПР вариантов раскроя наилучшее их сочетание, имеет широкое применение в практике раскроя не только линейного, но и плоскостного.


 

 

 

 

4.5. Постановка задачи дискретного программирования

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

Особый интерес к задачам ДП вызван тем, что во многих практических задачах необходимо находить целочисленное решение ввиду дискретности ряда значений искомых переменных. Например, мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев, если для их изготовления требуются заданные ресурсы, чтобы доход был максимален. При этом следует иметь ввиду, что выпуск спинок может принимать любое целое значение, подлокотники изготавливаются парами, а ножки должны быть кратными четырем.

Рассмотренную задачу распределения ресурсов с учетом требования дискретного значения переменных в общем виде можно записать так:

где

di1, di2, ..., dik - дискретные значения, которые может принимать переменная xi.

d i =

Данная постановка отличается от задачи распределения ресурсов линейного программирования

появлением булевых переменных и увеличением числа ограничений. На практике к задачам с булевыми переменными можно свести значительное число самых различных задач. Там, где есть варианты, из которых надо выбирать, задачу можно решать с помощью булевых переменных.

Выделяют два метода решения задач с булевыми переменными:

  1. Метод полного перебора. Алгоритм метода заключается в следующем:

  1. Решаются как обычные задачи целочисленного программирования, т.е. методом ветвей и границ. При этом на каждую переменную накладывается два ограничения: они должны быть в пределах 0Ј d iЈ 1; d i должны быть целыми.

 


 

 

 

 

4.6. Контрольные вопросы и задания

 

 


 

 

 

Фирма выпускает три продукта: A, B, C. На производство единицы продукта A требуется затратить 1,1 ч. труда ИТР, 12,3 ч. физического труда и 3,1 кг сырья. Для единицы продукта B соответствующие показатели равны 2,3 ч., 4,2 ч и 2,4 кг, для продукта C - 1,3 ч, 5,1 ч. и 1,2 кг. Ресурсы составляют 120 ч. труда ИТР, 640 ч. физического труда и 450 кг сырья. При оптовых закупках покупателю предоставляются скидки, так что прибыли от продажи продукции изменяются как показано в табл. 2.12. Например, если продается 120 ед. продукта A, то первые 40 ед. приносят по 63,2 руб. прибыли; следующие 60 - по 54,4 руб., а остальные 20 - по 48,3 руб. Сформулируйте задачу линейного программирования, решение которой определяет наиболее доходный производственный план.

Таблица 2.12.

Продукт А

Продукт B

Продукт C

Прода-жа, ед.

Удельная прибыль, руб.

Прода-жа, ед.

Удельная прибыль, руб.

Прода-жа, ед.

Удельная прибыль, руб.

0-40

63,2

0-50

36,5

0-100

30,5

40-100

54,4

50-100

24,3

Более 100

24,8

100-150

48,3

Более 100

18,7

-

-

Более 150

42,1

-

-

-

-

 


 

 

 

Леспромхоз, имеющий лесопильный и фанерный цеха, столкнулся с проблемой наиболее рационального использования выделенной лесосеки. Чтобы получить 2,5 м3 коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м3 еловых и 7,5 м3 пихтовой древесины. Для изготовления 100 м2 фанеры требуется 5,1 м3 еловых и 10,2 м3 пихтовой древесины. Выделенная лесосека содержит 80 м3 еловых и 180 м3 пихтовой древесины. Согласно условиям поставок, в течении планируемого периода необходимо произвести по крайней мере 10 м3 пиломатериалов и 1200 м2 фанеры. Доход с 1 м3 пиломатериалов составляет 80,2 руб., а со 100 м2 фанеры - 302,5 руб. Оптимизировать использование лесосеки.


 

 

 

 

 

 

 

 

 

Мебельное предприятие выпускает три вида наборов мебели, книжные полки и тумбу под телевизоры. Характеристики каждого вида продукции приведены в табл. 2.13. При условии получения максимальной прибыли объем товарной пилопродукции должен составить не менее 459,31 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, число единиц которого и нормы затрат времени оборудования каждой группы на изготовление единицы каждого вида продукции приведены в табл. 2.13. Предприятие работает в две смены с эффективным временем работы каждой машины в 3945 ч. (коэффициент сменности 1,9). Оптимизировать производственную программу предприятия.

Таблица 2.13.

Показатель

Виды продукции

Набор мебели 1

Набор мебели 2

Набор мебели 3

Книж-ные полки

Тумба под теле-визор

Оптовая цена единицы изделия, тыс. руб

7,2

14,3

32,5

0,182

1,5

Прибыль от реализации, тыс. руб

2,4

4,5

60,3

0,06

0,45

Таблица 2.14

 

Наименование оборудования

 

Число, шт.

Виды продукции

Набор мебели

1

Набор мебели

2

Набор мебели

3

Книжные полки

Тумба под телевизор

Линия раскроя древесно-стружечных плит

2

0,068

0,096

0,207

0,018

0,042

Гильотинные ножницы

1

0,045

0,080

0,158

0,011

0,035

Линия облицо-вывания

2

0,132

0,184

0,428

0,020

0,060

Линия обрезания кромок

2

0,057

0,082

0,230

0,010

0,028

Лаконаливная машина

2

0,063

0,090

0,217

0,010

0,032

Полироваль-ные станки

4

0,170

0,280

0,620

0,020

0,096


 

В леспромхозе производится раскряжевка хлыстов на сортименты. Требуется получить сортименты трех видов - длиной 6, 2,2 и 1,5 м. Длина среднего хлыста 31 м, средний диаметр 0,3 м. План поставки сортиментов, соответственно, 32,4 тыс. м3, 86,3 тыс м3 и 40,3 тыс. м3. Используя карту раскроя хлыстов без учета толщины пропила (табл.2.15) определить оптимальный план раскроя.

Таблица 2.15

Сорти-

мент, м

Варианты раскроя хлыстов

1

2

3

4

5

6

7

8

9

10

11

6

2,2

1,5

5

0

0

4

2

1

4

1

3

3

5

1

3

0

8

2

4

6

2

1

11

1

9

3

1

2

13

0

10

6

0

1

19

Отходы

1

1,1

0,3

0,5

1,0

1,2

0,3

0,7

1,1

0

0,3

 


 

 

 

 

Нижний склад производит два вида продукции: обрезную доску и брус. Для изготовления 1 м3 бруса требуется 2,5 м3 сосны или 3,3 м3 ели. Для изготовления 1 м3 доски требуется 3,2 м3 сосны или 3,5 м3 ели. Максимальные суточные запасы сосны - 250 м3, ели - 330 м3. Суточный спрос на брус - 110 м3, на доску - 150 м3 при оптовых ценах за 1 м3 бруса - 241 руб., за 1 м3 доски - 352 руб. Определить оптимальные объемы выпуска бруса и доски.

 


 

 

 

 

 

 

 

 

Лесхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц вещества A и 12 единиц B. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальны (по данным табл. 2.16).

Таблица 2.16

Питательные

вещества

 

Количество питательных веществ в 1 кг корма вида:

1

2

A

B

2

2

1

4

Цена 1 кг корма, руб

2

3


 

 

 

 

 

 

 

В деревообрабатывающий цех завода поступил заказ вырезать из фанеры заготовки двух видов для 530 изделий. Известно, что на одно изделие идет две заготовки первого вида и 3 - второго. На складе имеется 800 листов. Существуют три способа раскроя: при первом способе из листа фанеры получается 3 заготовок 1 вида и 2 заготовки 2 вида, при втором: 1 заготовка первого вида и 2 заготовки второго и при третьем - соответственно 2 и 2. Сколько листов фанеры надо выкроить по каждому способу, чтобы выполнить заказ и расход фанеры был минимальным?

 


 

 

 

 

 

Леспромхоз имеет древесину трех видов в количествах: 1 - 1,12 тыс. м3, 2 - 0,52 тыс. м3, 3 - 0,73 тыс. м3, для изготовления изделий A, B, C и D. Нормы расхода древесины в м3 на изготовление единицы каждого изделия и прибыль от реализации единицы изделия даны в табл. 2.17. Определить, сколько изделий каждого вида должно произвести предприятие, чтобы общая прибыль от реализации всех изделий была максимальной?

Таблица 2.17

Сырье

Нормы расхода сырья на единицу изделия

 

A

B

C

D

1

2

3

0,1

0,2

0,4

0,15

0,4

0,5

0,2

0,3

0,1

0,25

0,1

0,2

Прибыль, руб

13,4

24,2

33,7

11,1

 


 

 

 

Производство двух видов лесопродукции должно пройти три операции. Затраты времени на каждой операции на одно изделие, прибыль от реализации одного изделия в табл. 2.18. Сколько изделий каждого вида должно произвести предприятие, чтобы получить максимум прибыли, причем число изделий A должно быть не менее 10, а B - не более 70 единиц.

Таблица 2.18

Изделия

 

Затраты на одно изделие

Прибыль,

руб

1

2

3

A

B

11,3

6,1

7,2

8,3

16,1

9,5

25,5

38,3

Фонд времени на каждую операцию

600

700

1300

 

 

 


 

 

Предприятие должно выпустить по плану продукции A - 545 единиц, B - 367 единиц, C - 457 единиц на двух машинах. Каждая из двух машин может выполнить операции по производству всех трех видов продукции. Затраты времени на производстве единицы изделия каждой из двух машин приведены в табл. 2.19. Как распределить работу машин, при условии выпуска продукции пакетами по 100 шт. каждый, чтобы затраты времени на выполнение плана были минимальны?

Таблица 2.19

Машины

 

Продукция

A

B

C

1

2

4,3

6,2

10,7

8,5

10,4

20,2

 


 

 

 

Предприятию задана программа по изготовлению четырех видов изделий в количествах: вида A - 495, B - 265, C - 378, D - 162. На предприятии имеется три группы станков с различной производительностью. Задается суммарное допустимое время работы за этот период для каждой группы станков: первой - 80 ч., второй - 100 ч., третьей - 150 ч. Нормы времени (в часах) на изготовление одного изделия на каждом станке и данные об издержках (в рублях) на изготовление каждого изделия на станках различных групп приводятся в табл. 2.20. Требуется так распределить изготовление изделий по группам станков, чтобы была обеспечена заданная программа по изготовлению изделий и чтобы общие издержки были минимальны?

Таблица 2.20

Группы станков

 

Нормы времени на

станках, час

Издержки на изготовление единицы изделия, руб

1

2

3

4

A

B

C

D

1

11

111

0,5

0,4

0,4

0,3

0,2

0,1

0,4

0,2

0,3

0,1

0,5

0,6

0,12

0,15

0,18

0,25

0,15

0,35

0,3

0,4

0,5

0,4

0,2

0,1

 





Начальная страница. Содержание
Введение    Цели и задачи     Методологические основы     Линейное программирование     Нeлинейное программирование     Нeлинейное программирование: Безусловная однопараметрическая оптимизация     Нeлинейное программирование: Безусловная многопараметрическая оптимизация    Нeлинейное программирование: Условная многопараметрическая оптимизация    Целочисленное и дискретное программирование     Динамическое программирование     Принятие решений в условиях неопределенности     Принятие многоцелевых решений     Марковские процессы принятия решений     Литература