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

Цель задачи

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

Дано

• Два склада с запасами: 150 и 200 единиц.
• Четыре потребителя с потребностями: 100, 80, 90, 80 единиц.
• Матрица стоимостей перевозок (в условных единицах):

Ограничения по грузоподъемности маршрутов

• Первые два маршрута: до 50 единиц.
• Следующие два маршрута: до 65 единиц.
• Последние два маршрута: до 70 единиц.

Переменные

\( x_{ij} \) — количество груза, перевозимого от \( i \)-го склада к \( j \)-му потребителю.

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

$$ \text{Minimize } Z = \sum_{i=1}^{2} \sum_{j=1}^{4} c_{ij} x_{ij} $$

Ограничения

1. Баланс запасов: $$ \sum_{j=1}^{4} x_{ij} = a_i, \quad i = 1, 2 $$
2. Баланс потребностей: $$ \sum_{i=1}^{2} x_{ij} = b_j, \quad j = 1, 2, 3, 4 $$
3. Ограничения по грузоподъемности: $$ x_{ij} \leq d_{ij}, \quad \text{где } d_{ij} \text{ — грузоподъемность маршрута} $$
4. Неотрицательность переменных: $$ x_{ij} \geq 0, \quad \forall i, j $$
5. Целочисленность переменных: $$ x_{ij} \in \mathbb{Z}, \quad \forall i, j $$

Где:

• \( x_{ij} \) — количество груза, перевозимого от \( i \)-го склада к \( j \)-му потребителю
• \( a_i \) — запас на \( i \)-м складе
• \( b_j \) — потребность \( j \)-го потребителя
• \( d_{ij} \) — максимальная грузоподъемность маршрута

Подходы к расчету ограничений по грузоподъемности маршрутов

Определение стоимости перевозки (матрицы C)

Решение транспортной задачи в MATLAB

clear; clc; clf;

% Исходные данные
c = [10 25 15 25;
 22 22 25 28]; % матрица стоимостей 2x4

% Целевая функция
f = c(:);

% Целочисленные переменные
intcon = 1:8;

% Ограничения неравенства
A = [];
b = [];

% Ограничения равенства
Aeq = [1 0 1 0 1 0 1 0; % баланс склада 1
 0 1 0 1 0 1 0 1; % баланс склада 2
 1 1 0 0 0 0 0 0; % баланс пункта 1
 0 0 1 1 0 0 0 0; % баланс пункта 2
 0 0 0 0 1 1 0 0; % баланс пункта 3
 0 0 0 0 0 0 1 1]; % баланс пункта 4

beq = [150; 200; 100; 80; 90; 80];

% Границы
lb = zeros(8,1);
ub = inf(8,1);

% Специальные ограничения
ub(1:2) = 50; % первые два маршрута
ub(5:6) = 50; % следующие два маршрута
ub(3:4) = 70; % следующие два маршрута
ub(7:8) = 70; % последние два маршрута

% Настройка решателя
options = optimoptions('intlinprog',...
 'Display', 'off');

% Решение задачи
x = intlinprog(f, intcon, A, b, Aeq, beq, lb, ub, [], options);

% Форматирование результатов
x_matrix = reshape(x, 2, 4);

% Вывод результатов
disp('Оптимальный план перевозок:');
disp(x_matrix);

% Расчет стоимости
total_cost = sum(sum(x_matrix .* c));
fprintf('Минимальная стоимость: %.2f\n', total_cost);

% Проверка баланса
supply = sum(x_matrix, 2)';
demand = sum(x_matrix, 1);

disp('Проверка баланса:');
disp(['Запасы: ', num2str(supply)]);
disp(['Потребности: ', num2str(demand)]);

% Проверка целочисленности
if all(abs(x - round(x)) < 1e-6)
 disp('Все переменные целочисленные - OK');
else
 warning('Обнаружены дробные значения в решении!');
end