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

Предмет: Исследование операций

Раздел предмета: Транспортная задача

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

Постановка задачи:

• Есть количество грузов доступное для отправки из грузовых пунктов \( b = (3, 17, 18, 12) \).
• Есть потребности в грузах в пунктах выгрузки \( a = (19, 11, 20) \).
• Стоимость перевозки между каждым пунктом отправки и пунктом выгрузки задается матрицей транспортных издержек: \[ C = \begin{pmatrix} 1 & 2 & 50 & 4 \\ 6 & 3 & 1 & 40 \\ 25 & 4 & 9 & 7 \end{pmatrix} \]
• Требуется найти сколько единиц груза \( x_{ij} \) нужно перевезти от каждого пункта загрузки \( i \) до каждого пункта выгрузки \( j \), чтобы минимизировать общие затраты.

Переменные:

• \( x_{ij} \) — количество груза, которое надо перевезти из \( b_i \) в \( a_j \).

Оптимизационная цель:

Нам нужно минимизировать общие затраты:

\[ Z = \sum_{i=1}^{3}\sum_{j=1}^{4} C_{ij} \cdot x_{ij} \]

Условия:

1. Количество груза, отправляемого из каждого пункта загрузки, не может превышать имеющегося запаса: \[ \sum_{j=1}^{4} x_{ij} \leq b_i \quad \forall i \]
2. Количество груза, доставляемого в каждый пункт выгрузки, должно быть равно \( a_j \): \[ \sum_{i=1}^{3} x_{ij} = a_j \quad \forall j \]

Написание кода для LPSolve

Мы воспользуемся пакетом lpsolve для решения линейной транспортной задачи.

min: x11 * 1 + x12 * 2 + x13 * 50 + x14 * 4 + x21 * 6 + x22 * 3 + x23 * 1 + x24 * 40 + x31 * 25 + x32 * 4 + x33 * 9 + x34 * 7;

* Ограничения на поставки из пунктов загрузки
x11 + x12 + x13 + x14 = 0;
x14 >= 0;
x21 >= 0;
x22 >= 0;
x23 >= 0;
x24 >= 0;
x31 >= 0;
x32 >= 0;
x33 >= 0;
x34 >= 0;

Детальное объяснение:

1. Минимизируемая функция (Minimize): Это целевая функция, представляющая общие транспортные затраты потенциального плана. В каждом элементе этот член указывает на количество товаров \( x_{ij} \), умноженное на стоимость доставки \( C_{ij} \). \[ Z = 1 \cdot x_{11} + 2 \cdot x_{12} + 50 \cdot x_{13} + 4 \cdot x_{14} + \ldots \]
2. Ограничения для пунктов загрузки: Гарантируем, что суммарное количество товаров, отправляемое из каждого пункта загрузки, не превышает имеющегося на складе количества: \[ x_{11} + x_{12} + x_{13} + x_{14} \leq 3 \]
3. Ограничения для пунктов выгрузки: Гарантируем, что количество товара, получаемого каждым пунктом выгрузки, должно точно соответствовать требованиям: \[ x_{11} + x_{21} + x_{31} = 19 \]
4. Неотрицательные переменные: Все переменные \( x_{ij} \geq 0 \), так как количество груза не может быть отрицательным.

Как решить это с помощью LPSolve:

Сохраните код в файл с расширением .lp (например, transport.lp) и запустите решение через любой интерфейс LPsolve.