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

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

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

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

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

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

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

Из всех возможных маршрутов выбрать тот, у которого самое большое звено будет наименьшим. Вместо стоимости 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) _{m x n} = 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)