Динамическое программирование (стр. 3 из 10)

Здесь возможны варианты:

- деталь ждет обработки на k -ом станке, тогда

- деталь не ждет обработки

-

при ^a_ij0 деталь j на i -ом станке не обрабатывается по технологии.

2) На одном станке нельзя одновременно обрабатывать две детали j и s . Моменты начала обработки двух деталей должны отстоять как минимум на длину обрабатывания детали, которая идет первой.

x_isij ( сначалаобрабатывается j)

Но мы не знаем, какая деталь идет первой, поэтому условия x_ijis ( сначалаобрабатывается s) альтернативные, т.е. работает одно или другое.

Чтобы реализовать эту ситуацию введем дополнительную целочисленную переменную ^y_ijk

.

Обозначим верхнюю границу продолжительности производственного цикла через T .

Тогда можно записать:

T aij 1 yijs xis xij aij (*) T ais yijs xij xis ais (**) xis xij T

Исследуем данную конструкцию:

А) ^x_ij ^x_is 0 . Ситуация невозможна, т.к. это означает одновременную обработку двух деталей на станке.

В (*) y _ijs 0 , (**) y _ijs 1 .

Б) xij xis 0 , то (*) yijs 0 ; (**) yijs {0,1} .

Значит ^y_ijs 0 (единственное возможное значение). В) xij xis 0 , то (*) yijs {0,1} ; (**) yijs 1 .

Значит ^y_ijs 1 (единственное возможное значение). Таким образом, формальная конструкция (*) и (**) реализует альтернативные условия.

3) Момент окончания обработки на j ой детали на i -ом станке не превышает искомую длину производственного цикла t : xij aij t . Целевая функция задачи f t min . Таким образом имеем модель: f min

xkjaij

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

Приведенная постановка является наиболее простой.

Ограничения задачи могут быть дополнены следующими:

- условиями на сроки окончания отдельных работ;

- требование учета различных проиводственных факторов (труд, материалы, оборудование);

- требование учета дополнительных производственных факторов, сопровождающих процесс производства – особенностей технологии.

В качестве критериев оптимальности в этой задаче может быть использованы и другие критерии, которые делятся на 2 группы:

1) критерии, зависящие от общей продолжительности обработки изделий. К ним относятся: минимум простоев оборудования; максимум показателя использования оборудования; минимум издержек на незавершенное производство

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

4) Модель задачи о покрытии.

Задача о покрытии

Общий вид: n

c _j x _j min

j 1 n

a _ij x _j b _i , i 1, m

j 1

x _j {0,1}, a _ij {0,1}

Если ^c_j 1, j, то простая задача о покрытии; если ^c_j R , то взвешенная задача о покрытии.

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

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

Неоднородная ТЗ с фиксированными доплатами

В качестве задачи с разрывной функцией цели рассмотрим ТЗ с фиксированными доплатами или неоднородную ТЗ.

Постановка: i 1, m - пункты производства, ^a_i - объемы производства; j 1, n - пункты назначения, ^b_i - потребности.

Кроме того, по условиям перевозки требуется дополнительно платить ^d_ij ден.ед. независимо от величины груза в случае, если груз перевозится из i в j .

Интерпретация доплаты ^d_ij может быть: плата за аренду авто, дорожный сбор на крупных дорожных сооружениях, таможенная политика и т.д.

Модель. В связи с новыми условиями целевая функция ТЗ становится принципиально другой. Это функция, в которой прежнее ^c_ij становится зависимой от того, перевозится груз или нет.

Здесь переменных целочисленных нет.

Чтобы численно реализовать такую модель сведем ее к ЧЦЗ. - определим величины Mij min{ ai, bj} i, j

-

введем переменные ^y_ij {0,1} и условия ^x_ij^M_ij ^y_ij .

m n

Тогда F ( cij xij dij yij ) .

i 1 j 1

Рассмотрим, как работает в оптимальном плане:

- если yij 0 , то xij 0 ;

- если yij 1 , то xij Mij неравенство излишнее (по построению);

-

если xij 0 , то yij должен быть нулем, иначе план не оптимальный и его можно улучшить; - Если xij 0 , то yij 1 .

Таким образом, переменные ^y_ij {0,1} «согласуют» плату за аренду и действие – осуществление перевозки.

В схему ТЗ с фиксированными доплатами укладывается также задача о смесях, имеющие фиксированные доплаты (фиксированная стоимость заказа, компоненты смеси, не зависящие от заказываемого количества).

Распределительная задача (обобщенная ТЗ)

Рассматривается транспортное предприятие с j 1, n транспортными линиями (маршрутами). В соответствии с планом графика по j -ой линии надо выполнить ^b_j рейсов.

Фонд наличных транспортных средств (транспортный парк) представлен i 1, m типами транспортных единиц с полными резервами времени ^a_i .

Заданы затраты времени на выполнение i -ой транспортной единицей рейса j - ^t_ij и затраты денежных средств ^c_ij .

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

Введем обозначение: ^x_ij - количество i -го транспорта на j -ом маршруте.

Модель:

(2)

(3)

(4)

Распределительная задача с фиксированными доплатами

Пусть дополнительно в постановке обобщенной ТЗ нужно учесть следующее: выпуск транспортных средств i на маршрут j связан с дополнительными затратами времени

, не зависящие от числа рейсов, и денежных средств ^d_ij .

Тогда затраты средств ^c_ij будут зависеть от того, будет ли транспортное средство i содержать хотя бы один рейс по маршруту j или нет.

Таким образом: ^c_ij (5)

dij , xij

Аналогично, для затрат времени: ^t_ij ( ^x_ij )

(6)

Получили модель: