Построить математическую модель транспортной задачи

Данное задание относится к предмету "математическое программирование", а именно к разделу "транспортные задачи".

1. Построение математической модели:

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

• Пусть $\text{(}{a}_i\text{)}$ — запасы в источниках ($i=1,2,...,m$).
• Пусть $\text{(}{b}_j\text{)}$ — потребности в пунктах назначения ($j=1,2,...,n$).
• Пусть $\text{(}{c}_{ij}\text{)}$ — стоимость транспортировки единицы груза от $i$-го источника к $j$-му потребителю.
• Пусть $\text{(}{x}_{ij}\text{)}$ — количество единиц груза, отправляемых от $i$-го источника к $j$-му потребителю.

Цель: Минимизировать общую стоимость транспортировки:

$\text{[}\sum _{i=1}^m\sum _{j=1}^n{c}_{ij}{x}_{ij}\text{]}$

При ограничениях:

• $\text{(}\sum _{j=1}^n{x}_{ij}=a_i\text{)}$ для каждого источника $i$.
• $\text{(}\sum _{i=1}^m{x}_{ij}=b_j\text{)}$ для каждого пункта назначения $j$.
• $\text{(}{x}_{ij}\ge 0\text{)}$.

2. Привести задачу к сбалансированному виду:

Для сбалансированной задачи сумма всех запасов должна быть равна сумме всех потребностей ($\text{(}\sum a_i=\sum b_j\text{)}$). Если это не так, нужно добавить фиктивного источника или пункт назначения.

Посмотрим на задание (по изображению):

• Сумма предложений (запас): $90+130+50+100=370$
• Сумма потребностей: $70+90+110+80+110=460$

Так как $\text{(}\sum a_i=370\ne \sum b_j=460\text{)}$, добавим фиктивный источник с запасом $90$ единиц, делая задачу сбалансированной.

3. Метод северо-западного угла:

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

4. Метод минимального элемента:

Выбираем ячейку с минимальной стоимостью $\text{(}{c}_{ij}\text{)}$ и назначаем максимальное возможное количество, аналогично методу северо-западного угла, повторяя процесс.

Пожалуйста, предоставьте количество запасов и потребностей для выполнения расчёта более детально.