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

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

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

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

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

б) задача с запретами не имеет планов

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

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

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

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

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

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

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

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 с условием целочисленности

A) задачи с неделимостями

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

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

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

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

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

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

B) задача коммивояжера

Есть 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

C) задача о назначениях

n работ

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

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

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

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

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