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

Пусть имеется n поставщиков однородной продукции (a_i) и m потребителей этой продукции (b_j). Каждый поставщик может поставлять свою продукцию любому из потребителей. Известны затраты C_ij на перевозку единицы продукции от каждого поставщика к каждому потребителю. Необходимо так распределить перевозки, чтобы суммарные затраты были минимальными. Элементы решения – Х_ij количество продукции, перевозимой от каждого поставщика к каждому потребителю.

Структурная схема данной задачи в сетевой постановке приведена на рисунке 3.1.

Рисунок 3.1 – Пример структурной схемы транспортной задачи

Обозначим A_i возможности поставщиков и B_j потребности потребителей.

Составим математическую модель задачи.

Ограничения по производственным мощностям поставщиков:

Ограничения по производственным мощностям потребителей:

Целевая функция – требование минимизации суммарных затрат на перевозки:

В краткой форме записи эта модель имеет вид:

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

3.2.2 Построение исходного опорного плана

Опорный план является основой для оптимизации процесса. Существует несколько способов его построения. Один из них – метод северо-западного угла – наиболее прост, но и наименее эффективен, второй – метод наименьшего элемента несколько сложнее, но значительно ближе к оптимальному.