4.5. Задача планирования производства при фиксированном фонде времени
Суть задачи состоит в следующем. На предприятии действуют различные технологии, которые могут выпускать различные виды изделий, работая при этом с разной производительностью. С другой стороны, отдельные виды изделий могут изготавливаться по разным технологиям. Запланировано к выпуску определенное количество изделий заданного вида. На каждую технологию задан общий расход некоторого ресурса (например, суммарного времени работы). Необходимо так распределить объемы работ по технологиям, чтобы было полное использование мощностей технологий с максимально возможной экономией фонда времени.
Введем обозначения:
Pi – тип изделия, i = 1,…, m;
Тi – тип технологии (способ изготовления изделий), j = 1,…, n;
tij – время изготовления одного изделия i-го типа по j-му способу (удельное время);
хij – планируемое число изделий i-го типа по j-му способу (переменные управления);
Ai – план изделий i-го типа;
Bj – фонд времени для j-й технологии.
Модель ЛП
при ограничениях:
(1)
(2)
Такая модель хорошо интерпретируется по смыслу задачи. Но задача в такой модели может оказаться некорректной. Это значит, что решения, удовлетворяющего всем неравенствам (2) одновременно, может не существовать. Попытка же удовлетворить неравенствам приводит к нарушению равенств (1). Это произойдет, если хотя бы одно плановое задание Ai завышено.
Отсюда следует, что симплекс-метод для решения этой задачи в общем случае не годится, так как в нем не предусмотрена коррекция плановых заданий Ai. Нужен другой алгоритм.
Решение задачи
(эвристический алгоритм)
Алгоритм основан на введении меры предпочтения одной технологии перед другими для каждого вида изделий посредством нормировки tij – индекса Iij для фиксированного i.
Шаг 0. Исходные данные для задачи: все tij, Ai и Bj.
Пример задания исходных данных:
Тип изделия | Задание Ai | Удельное время по технологиям | ||||
Т1 | Т2 | Т3 | Т4 | |||
Р1 | 400 | 2 | 1 | – | 2 | |
Р2 | 100 | 3 | 2 | – | 1 | |
Р3 | 400 | – | – | 1 | 2 | |
Р4 | 160 | 3 | – | 2 | 2 | |
Фонд времени Bj | 240 | 330 | 200 | 560 |
Шаг 1. Индексация элементов матрицы удельных затрат:
В результате каждый минимум в строке заменен нулем (перспективная клетка), а все элементы матрицы выдержаны в едином масштабе.
Шаг 2. Загрузка таблицы ||хij|| в перспективные клетки. Пусть Fij – общее время изготовления хij изделий (i, j – фиксированы):
Fij = tij · хij = ·Ai.
В результате возникает исходный план.
Шаг 3. Оценка оптимальности плана. Производится расчетом баланса суммарного времени для каждой технологии, т.е. по столбцам матрицы ||хij||:
Если баланс нулевой, т.е. все ΔFj = 0, то КОНЕЦ.
Если баланс одного знака для всех технологий, т.е. по всем ΔFj, то переход к шагу 5. Иначе – переход к шагу 4.
Шаг 4. Перезагрузка технологий. Здесь осуществляется переход от перегруженной технологии (ΔFj < 0) к недогруженной (ΔFj > 0) по отдельным видам изделий. Переход к шагу 3.
Баланс (ΔFj < 0) означает нарушение соответствующего неравенства в модели задачи, которое компенсируется за счет другой подходящей технологии. Шаг 4 осуществляется в два этапа:
1. Куда перегружать (правило 1).
2. Сколько изделий перегружать (правило 2).
Правило 1. Разгружается та клетка данного столбца с отрицательным балансом, которая имеет наименьшую разность индексов с клеткой из столбца с положительным балансом, но из той же строки (т.е. для одного и того же вида изделий).
Правило 2. Объем перезагрузки определяется минимально возможной перезагрузкой избыточного и перегруженного столбцов при достижении нулевого баланса в одном из них.
Шаг 5. Коррекция плана. Плановые задания по изделиям сокращаются или увеличиваются в зависимости от недостатка или избытка суммарного времени так, чтобы ΔFj = 0. Переход к шагу 3.
Замечания к решению задачи
1. В любой ситуации перезагрузка возможна только в столбец с положительным балансом (исключая поиск варианта конечного плана – см. п. 4).
2. Если наименьшие разности индексов равны, то выбирается тот столбец с отрицательным балансом, который имеет меньшее число вариантов перегрузки. Тем самым исключается заведомо лишний перебор.
3. При невозможности прямой перегрузки из перегруженного столбца в недогруженный следует использовать подходящий столбец с нулевым балансом как промежуточный.
4. Нулевая разность индексов приводит к варианту плана с тем же значением целевой функции. Это следует применять только к конечному плану для отыскания вариантов решения задачи.
5. Правило округления. В любом арифметическом выражении округление делается только конечного результата и только в меньшую сторону. Иначе конечный план может оказаться с отрицательным балансом, что недопустимо.
Yandex.RTB R-A-252273-3
- Б.К. Алабин
- 1.2. Основные понятия и определения исследования операций
- 1.3. Общая постановка задачи исследования операций
- Тема 2 индексный метод (теория графов)
- 2.1. Основные понятия и определения индексного метода (им)
- 2.2. Постановка задачи маршрутизации в им
- 2.3. Идея решения задачи
- 2.4. Алгоритм решения задачи с помощью произвольного дерева маршрутов
- 2.5. О порядковой функции
- 2.6. Общая теория индексного метода на матрице орграфа
- 2.7. Общий алгоритм решения задачи маршрутизации на матрице орграфа
- 2.8. Иллюстративный пример
- 2.9. Последовательные графы в им
- 2.10. Решение задачи распределения ресурсов индексным методом
- 3.4. Условия, которым должна удовлетворять задача, описываемая моделью дп
- 3.5. Вычислительная схема дп для обратного хода
- 3.6. Особенности вычислительной схемы дп для прямого хода
- 3.7. Основные достоинства метода дп
- 3.8. Типовые задачи в моделях дп
- Тема 4 методы линейного программирования (лп)
- 4.1. Систематизация моделей лп
- 4.2. Возможные исходы решения задач лп
- 4.3. Транспортная задача (т-задача)
- Метод потенциалов для оценки Δij в т-задаче
- Замечания к решению т-задачи
- 4.4. Задача «о назначениях»
- 4.5. Задача планирования производства при фиксированном фонде времени
- Иллюстративный пример
- Тема 5 задача и модель «черного ящика»
- 5.1. Общие замечания
- 5.2. Содержательная постановка задачи
- 5.3. Формальная постановка задачи
- 5.4. Математическая модель и математическая постановка задачи
- 5.5. О решении задачи
- 5.6. Иллюстративный пример
- Рекомендуемая литература
- Содержание