Постановка задачи и ее математическая модель

Рачковский, Н. Н.

Р 28 Математическое программирование: Транспортная задача: учеб.-метод. пособие / Н. Н. Рачковский. – Минск: Частн. ин-т управ.
и предпр., 2007.– 29 с.

Рассматриваются обеспечение разрешимости транспортной задачи и построение начального плана перевозок. Дается теоретическое обоснование метода потенциалов. Приводится решение транспортной задачи.

Для студентов Частного института управления и предпринимательства.

УДК 004.4

ББК 32.973-018

© Рачковский Н. Н., 2007

© Частный институт управления и предпринимательства, 2007

План:

1. Постановка задачи и ее математическая модель.

2. Обеспечение разрешимости транспортной задачи. Построение начального плана
перевозок.

3. Теоретическое обоснование метода потенциалов.

4. Алгоритм метода потенциалов.

5. Пример решения транспортной задачи.

6. Упражнения для самостоятельной работы.

Ключевые слова:

Постановка задачи и ее математическая модель

Пусть имеется m поставщиков А ₁, А ₂, …, А_m некоторого однородного груза, накопленного ими в объемах а ₁, а ₂, …, а_m соответственно. Пусть имеется n потребителей В ₁, В ₂, …, В_n со спросом на этот груз в объемах b ₁, b ₂, …, b_n. Известны тарифы перевозок C_ij – стоимость перевозки одной единицы груза от каждого поставщика А_j к каждому потребителю B_j. Требуется найти оптимальный план перевозок, обеспечивающий:

а) полный вывоз накопленного груза (по возможности) из всех пунктов поставки А ₁, А ₂, …, А_m;

б) полное удовлетворение спроса (по возможности) всех потребителей В ₁, В ₂, …, В_n;

в) минимальные транспортные расходы.

Условие такой задачи принято записывать в виде таблицы (табл. 1):

Таблица 1

	Потребители	Накопленный запас груза
Поставщики
Спрос

Чтобы решить сформулированную выше задачу с помощью математического аппарата, нужно составить математическую модель, создание которой осуществляется в три этапа:

1) выбор переменных;

2) создание целевой функции;

3) составление ограничений.

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

.

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

Вторую часть ограничений составим исходя из условия полного удовлетворения спроса всех потребителей . Ограничений будет столько, сколько имеется потребителей, т. е. n. С учетом условия задачи и выбранных переменных получим следующие ограничения:

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

Построенная математическая модель является задачей линейного программирования, поэтому может быть решена симплекс–методом. Из-за большого количества переменных и ограничений–уравнений даже при относительно небольших значениях m и n (например, при и получаем задачу линейного программирования с девятью переменными и шестью ограничениями–уравнениями) использование стандартного варианта симплекс–метода затруднено по причине большого количества громоздких вычислений. Однако специфичность ограничений-уравнений (каждая переменная присутствует только в двух уравнениях и только с коэффициентом +1) позволяет значительно упростить вычисления. Эти упрощения приводят к адаптированной модификации симплекс-метода, называемой методом потенциалов, которая используется при решении транспортной задачи.

2. Обеспечение разрешимости транспортной задачи.
Построение начального плана перевозок

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

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

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

Построение начального плана перевозок, а также улучшение имеющегося плана удобно производить на распределительной таблице: в правом верхнем углу каждой ее клетки указывается соответствующий тариф ,
в левых нижних углах клеток указываются загрузки – это соответствующее количество перевозимых грузов (табл. 2).

Таблица 2

	Потребители	Запас груза
В 1	В 2	…	Вn
Поставщики	A 1	c 11	c 12	…	c 1 n	а 1
А 2	c 21	c 22	…	c 2 n	а 2
	…	…	…	…
Am	сm 1	сm 2	…	сmn
Спрос	b 1	b 2	…	bn

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

Согласно методу северо-западного угла, загрузка распределительной таблицы (построение начального плана перевозок) начинается с клетки
(1; 1), соответствующей поставщику с запасом груза и потребителю со спросом . Загрузку этой клетки требуется выбрать так, чтобы либо полностью вывезти весь накопленный запас груза из пункта поставки , либо полностью удовлетворить спрос потребителя , либо и то, и другое одновременно. Поэтому клетку (1; 1) загрузим минимальным из чисел , , т. е. числом . Затем возникает вопрос о выборе следующей клетки для загрузки. Каждый раз такой выбор должен осуществляться на основе следующего правила: нужно сложить загрузки всех уже загруженных клеток графы, в которой находится последняя загруженная клетка, и сравнить эту сумму со спросом в данной графе (самая нижняя строка). Если окажется, что вычисленная сумма загрузок меньше соответствующего спроса, то следующая загружаемая клетка будет находиться ниже последней загруженной клетки, в противном случае – справа от нее.

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

Для контроля правильности построения начального плана перевозок нужно иметь в виду следующее:

1) в полностью построенном начальном плане перевозок должно быть загружено ровно клеток;

2) сумма загрузок всех клеток в каждой строке должна быть равна соответствующему запасу груза;

3) сумма загрузок всех клеток в каждой графе должна быть равна соответствующему спросу.