Задача о контроле качества продукции на конвейере

На конвейере производится некоторый продукт, процесс производства состоит из n последовательных операций. После каждой операции возможен контроль качества. Продукт поступает на конвейер партиями (≥ 1 штук в одной партии).

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

Заданы следующие параметры: стоимость выполнения каждой операции на одном экземпляре продукции; фиксированная стоимость контроля одной партии продукта после операции j, при условии, что предшествующий контроль проводился после операции i; стоимость контроля единицы продукта после операции j, при условии, что предшествующий контроль проводился после операции i. Контроль должен определить все дефекты, которые были сделаны на всех промежуточных этапах i+1, i+2,... j.

Требуется составить оптимальный план контроля качества, который указывает, после каких операций нужно проводить контроль, при этом суммарные затраты на производство партии и её контроль должны быть минимальны.

Математическую модель задачи можно посмотреть в книге [5].

Задачи для самостоятельного решения.

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

Вариант 1

Задача 1.1

Задана схема возможных маршрутов движения от пункта А до пункта B (рис. 21). Стоимость переезда из пункта i в пункт j известна и равна c_ij. Требуется определить такой путь из пункта А в пункт B, общая стоимость передвижения по которому будет минимальной. Изменится ли стоимость и оптимальный маршрут, если дорога от пункта 5 к пункту 7 будет перекрыта?

A

B

Рис.21

Задача 2.1

Найти оптимальное распределение средств между 4 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией вложенных в него средств x. Вложения кратны 1, функции f(x) заданы таблично. Цель: максимизация суммарной прибыли.

x
f1(x)	0,2	0,9	1,0	1,2	2,0
f2(x)	1,0	1,1	1,3	1,4	1,8
f3(x)	2,1	2,5	2,9	3,9	4,9
f4(x)		2,0	2,5	3,0	4,0

Задача 1.3

Решить задачу об оптимальном распределении ресурсов в количестве S₀=100000 усл .ед. между двумя отраслями в течение 4 лет, если прибыль, не возвращаемая в производство, определена функциями , и средства, возвращаемые для дальнейшего распределения, определяются функциями . Все возвращенные средства перераспределяются на следующий год.

Задача 1.4

Составить графическую модель и решить задачу на определение оптимальных сроков замены оборудования. Первоначальная стоимость оборудования p₀=6000, ликвидная стоимость , стоимость содержания в течение года оборудования возраста t лет равна , n=4 – срок эксплуатации, в конце которого оборудование продается. Критерием оптимальности являются суммарные затраты на эксплуатацию оборудования в течение n лет с учетом первоначальной покупки и конечной продажи.

Задача 1.5

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

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

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

Задача 1.6

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

Рис.22

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

Вариант 2

Задача 2.1

Задана схема возможных маршрутов движения из пункта А в пункт Б (рис.23). Время переезда из пункта i в пункт j известно и равно t_ij (ч). В каждом пункте путешественник делает остановку на время T=1 (ч). Требуется определить минимальное время, за которое путешественник доберется от пункта А до пункта B, и соответствующий маршрут.

А

В

Рис.23

Задача 2.2

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

x
f1(x)	0,5	0,9	1,3	2,4	3,5	4,8
f2(x)	0,7	0,9	1,1	2,3	3,6	4,9
f3(x)	0,6		1,3	2,5	3,6	4,7

Задача 2.3

Решить задачу об оптимальном распределении ресурсов в количестве S₀=50000 усл .ед. между двумя отраслями в течение 4 лет, если прибыль, не возвращаемая в производство, определена функциями , и средства, возвращаемые для дальнейшего распределения, определяются функциями . Все возвращенные средства перераспределяются на следующий год.

Задача 2.4

Составить графическую модель и решить задачу на определение оптимальных сроков замены оборудования. Первоначальная стоимость оборудования p₀=6000, ликвидная стоимость и стоимость содержания в течение года оборудования возраста t лет заданы таблично, n=5 – срок эксплуатации, в конце которого оборудование продается. Критерием оптимальности являются суммарные затраты на эксплуатацию оборудования в течение n лет с учетом первоначальной покупки и конечной продажи.

t
φ (x)
r (x)

Задача 2.5

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

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

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

Задача 2.6

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

Рис.24

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

Вариант 3

Задача 3.1

Задана схема возможных маршрутов движения из пункта А в пункт Б (рис.25). Расстояния между пунктами (в км) известны и указаны на схеме. Средний расход топлива для легкового автомобиля 8 литров на 100 км. Определить такой путь из пункта А в пункт Б, для которого расход топлива будет минимальным.

А

Б

Рис.25

Задача 3.2

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

x
f1(x)
f2(x)
f3(x)

Задача 3.3

Решить задачу об оптимальном распределении ресурсов в количестве S₀=200000 усл .ед. между двумя отраслями в течение 5 лет, если прибыль, не возвращаемая в производство, определена функциями , и средства, возвращаемые для дальнейшего распределения, определяются функциями . Все возвращенные средства перераспределяются на следующий год.

Задача 3.4

Составить математическую модель, записать уравнения Беллмана и решить графически задачу на определение оптимальных сроков замены оборудования с целью минимизации суммарных затрат. Стоимость нового оборудования зависит от года покупки , стоимость содержания оборудования возраста t в течение года равна , его ликвидная стоимость , – срок эксплуатации, в конце которого оборудование продается.

Задача 3.5

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

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

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

Задача 3.6

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

Рис.26

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

Вариант 4

Задача 4.1

Задана схема возможных маршрутов движения между пунктами А в B (рис.27). Время переезда из пункта i в пункт j известно и равно t_ij (ч). Предполагается, что в каждом промежуточном пункте путешественник находится одинаковое время T=1 (ч). Требуется определить минимальное время, за которое путешественник доберется от пункта А до пунктаB и вернется обратно, и соответствующий маршрут. Причем обратный путь из пункта B до пункта A должен отличаться от пути из пункта A до пункта B (промежуточные пункты по маршрутам «туда» и «обратно» могут повторяться). Время нахождения путешественника в пункте B равно 8 часам. Какие пункты путешественник не посетит?

А

В

Рис.27

Задача 4.2

Решить задачу об оптимальном распределении ресурсов в количестве 30 усл .ед. между тремя предприятиями. Эффективность использования средств задана в таблице. Вложения кратны 5. Цель: максимизация суммарной прибыли.

x	f1(x)	f2(x)	f3(x)

Задача 4.3

Решить задачу об оптимальном распределении ресурсов в количестве S₀=100000 усл .ед. между двумя отраслями в течение 4 лет, если прибыль, не возвращаемая в производство, определена функциями , и средства, возвращаемые для дальнейшего распределения, определяются функциями . Все возвращенные средства перераспределяются на следующий год. Дополнительно в начале каждого года для распределения добавляются средства в количестве D=20000 усл .ед.

Задача 4.4

Составить математическую модель, записать уравнения Беллмана,составить графическую модель и решить задачу на определение оптимальных сроков замены оборудования. Первоначальная стоимость оборудования p₀=8000, ликвидная стоимость и стоимость содержания в течение года оборудования возраста t лет заданы таблично, – срок эксплуатации, в конце которого оборудование продается. Критерием оптимальности являются суммарные затраты на эксплуатацию оборудования в течение n лет с учетом первоначальной покупки и конечной продажи.

t
φ (x)
r (x)

Задача 4.5

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

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

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

Задача 4.6

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

Рис.28

Вариант 5

Задача 5.1

Задана схема возможных маршрутов движения из пункта А в пункт B (рис.29). Расстояния между пунктами (в км) известны и указаны на схеме. Средний расход топлива для грузового автомобиля 15 литров на 100 км. Определить минимальный расход топлива и соответствующий оптимальный маршрут из пункта А в пункт B.

А

В

Рис.29

Задача 5.2

Решить задачу об оптимальном распределении ресурсов в количестве 25 усл .ед. между тремя предприятиями. Эффективность использования средств задана в таблице. Вложения кратны 5. Цель: максимизация суммарной прибыли.

x	f1(x)	f2(x)	f3(x)

Задача 5.3

Решить задачу об оптимальном распределении ресурсов в количестве S₀=40000 усл .ед. между двумя отраслями в течение 4 лет, если прибыль, не возвращаемая в производство, определена функциями , и средства, возвращаемые для дальнейшего распределения, определяются функциями . Все возвращенные средства перераспределяются на следующий год. Дополнительно в начале каждого года для распределения добавляются средства в количестве D=10000 усл .ед.

Задача 5.4

Составить графическую модель и решить задачу на определение оптимальных сроков замены оборудования. Первоначальная стоимость оборудования p₀=8000, стоимость содержания в течение года оборудования возраста t лет равна , ликвидная стоимость , n=5 – срок эксплуатации, в конце которого оборудование продается. Критерием оптимальности являются суммарные затраты на эксплуатацию оборудования в течение n лет с учетом первоначальной покупки и конечной продажи.

Задача 5.5

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

Рабочее место линии 1
Время операции
Время перемещения изделия на линию 2 после прохождения рабочего места
Рабочее место линии 2
Время операции
Время перемещения изделия на линию 1 после прохождения рабочего места
Время от момента подачи начальной заготовки на линию до начала первой операции
Время от момента окончания последней операции до снятияготового изделия с линии

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

Задача 5.6

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

Рис.30

Список литературы

1. Bellman, R.On the Theory of Dynamic Programming, Proceedings of the National Academy of Sciences, 1952.

2. Bellman, R.E. Dynamic Programming. Princeton University Press, Princeton, NJ. 1957. Republished 2003: Dover.

3. Вентцель, Е. С. Исследование операций. Задачи, принципы, методология [Текст]: учеб. пос. / Е. С. Вентцель. – 3-е изд., стер. – М.: Дрофа, 2004. – 208 с.; ил.

4. Исследование операций в экономике [Текст]: учеб. пособие / под ред. Н. Ш. Кремера. – М.: ЮНИТИ, 2005. – 407 с.

5. Писарук, Н. Н. Исследование операций [Электронный ресурс] / Н. Н. Писарук. Минск : БГУ, 2015. – 304 c. Режим доступа http://pisaruk.narod.ru/books/OR.pdf (дата обращения 28.07.2017)

Учебное издание

Лукиных Ирина Григорьевна

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В РЕШЕНИИ
ЭКОНОМИЧЕСКИХ ЗАДАЧ

Учебно-методическое пособие

Подписано к использованию Заказ №

Федеральное государственное бюджетное образовательное учреждение высшего образования «Вятский государственный университет»

610000, Киров, ул. Московская, 36, тел.: (8332) 64-23-56, http://vyatsu.ru

y

xi-1

xi

x

xi-1+h/2

y=f(x)

Pi

Рис.3.4