Транспортная задача с запретами

– запреты (не от каждого поставщика к каждому потребителю можно сделать перевозку)

Чем больше запретов, тем сложнее осуществить перевозку и с некоторого момента задача может стать неразрешимой.

В новой задаче (с запретами):

1. – решение задачи с запретами

2. задача с запретами не имеет планов

Транспортная задача по критерию времени

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

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

Решение задачи – какое-то t.

Не является задачей линейного программирования, целевая функция – дискретная (не линейная).

18. Распределительные модели.

Задача о перевозке взаимозаменяемых продуктов

mпунктов производства топливаa_i– объём производстваi-го сорта топлива,i = 1, …,m

В каждом пункте производится один сорт топлива nпотребителей теплаb_j– количество тепла, необходимоеj-му потребителю,j = 1, …,n

λ_ij– коэффициент перехода отi-го сорта топлива кj-му потребителю. (Сколько килокалорий получается уj-го потребителя при сжиганийi-го сорта топлива)c_ij– удельные транспортные затраты, стоимость перевозкиi-го сорта топлива кj-му потребителю.

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

x_ij– искомый объём перевозки изi-го сорта топлива вj-му потребителю

– распределительная задача ЛП

Задача определения производственной задачи предприятия

mизделий нужно изготовитьa_i– план поi-му изделию,i = 1, …,m

nпредприятий

T– время выполнения заказаτ_j– объем работы времени наj-ом предприятии,j = 1, …,n

t_ij– время работы наj-ом предприятии для изготовления 1 единицыi-го изделия.c_ij– стоимость изготовления 1 единицыi-го изделия наj-ом предприятии.

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

x_ij– количество изделийi-го вида, изготовляемых наj-ом предприятии

Обозначим:

– свели к предыдущей задаче

Если все λ_ij= 1, то получим транспортную задачу.

Если все λ_ij=α_iβ_j(можно представить в виде такого произведения), то можно свести к ТЗ.

В этом случае r(λ_ij)_mxn= 1,r(А) =m+n,

19. Целочисленные линейные модели:

Переменные – целые числа.

– задачаLс условием целочисленности

1. задачи с неделимостями

Переменные определяют физически неделимые объекты. Задача о рюкзаке:

nпредметов есть в наличии (необязательно разных)p_j– весj-го предмета,j = 1, …,n

c_j– ценностьj-го предмета,

P– «грузоподъемность» рюкзака.

Требуется загрузить рюкзак набором предметов из данных nс максимальной суммарной ценностью.

Задача возникает при сборе чумадана в поездку, в инженерном проектировании, при загрузке космических кораблей.

2. задача коммивояжера

Есть n+ 1 городp₀,p₁, …,p_n. Задана матрица расстоянийc_ij=ρ(p_i,p_j).

Коммивояжер выезжая из города p₀, должен объехать все города, побывать в каждом из них ровно по одному разу и вернуться обратно вp₀

Как объехать города так, чтобы пройденное расстояние было минимальным.

Всего возможных маршрутов n(n– 1)…(n–k)…1 =n!, дляn= 13:n!= 6 227 020 800, то есть перебор не приемлем. Сводят к задаче целочисленного ЛП

– изp_iможно поехать только в один другой город

– вp_jможно приехать только из одного другого города

– не дает маршруту распасться

u_i=k, еслиp_iпосещается наk-ом шаге

uсуществует и можно брать изN

3. задача о назначениях

nработ

nкандидатов на выполнение.

Требуется распределить работы между кандидатами наиболее рациональным образом. c_ij– затраты, связанные с назначениемi-ой работыj-му кандидату

–i-ая работа может быть назначена только одному кандидату

–j-ый кандидат может выполнять только одну работу

Частный случай транспортной задачи, но сильно вырождена (матрица n xnизnединиц, ранг матрицыr(A) =n– 1)

4. модель рационального раскроя

Есть стандартные заготовки. Нужно:

1. Сделать требуемое количество шаблонов (видов деталей)

2. Затратить минимум заготовок (или другой вариант – минимизировать отходы)

Задачи бывают:

1. Одномерные (трубы, кабель…)

2. Двумерные (листы,…)

3. Трехмерные

Одномерный случай:

L– длина заготовки

mвидов деталиa_i– план по деталиi,i = 1, …,m

l_i– длинаi-ой детали

n – число способов раскроя

a_ij– количество деталейi-го вида, получаемых из одной заготовки, раскраиваемой по способыj.x_j– количество заготовок, раскраиваемых по способуj.

Ограничения в задаче:	Целевая функция:
	– если нужно затратить минимум заготовок – если нужно минимизировать отходы где

25