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

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

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

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

• Пусть \( a_i \) — запасы в источниках (i = 1, 2, ..., m).
• Пусть \( b_j \) — потребности в пунктах назначения (j = 1, 2, ..., n).
• Пусть \( c_{ij} \) — стоимость транспортировки единицы груза от i-го источника к j-му потребителю.
• Пусть \( x_{ij} \) — количество единиц груза, отправляемых от i-го источника к j-му потребителю.

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

\[\sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij}\]

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

• \(\sum_{j=1}^{n} x_{ij} = a_i\) для каждого источника i.
• \(\sum_{i=1}^{m} x_{ij} = b_j\) для каждого пункта назначения j.
• \(x_{ij} \geq 0\).

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

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

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

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

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

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

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

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

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

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