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

В решении первой подзадачи будем использовать метод транспортной задачи. Транспортная задача – это задачи с единой математической моделью. Данные задачи относятся к задачам линейного программирования. Однако матрица системы ограничений транспортной задачи своеобразна, и для ее решения разработаны специальные методы. Эти методы позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Целевая функция имеет вид:

,                                     (2.1)

где  – количество груза, перевозимого из -ого пункта отправления в -ый пункт назначения, тыс. т;

 – стоимость перевозки единицы груза из -ого пункта отправления в -ый пункт назначения, тыс.руб.

Существует система ограничений:

1) Сумма всех перевозок, стоящих в первой строке матрицы Х, должна равняться запасам первого поставщика, сумма перевозок во второй строке матрицы Х – запасам второго поставщика и т.д.:

Это означает, что запасы поставщиков вывозятся полностью.

2) Суммы перевозок, стоящих в каждом столбце матрицы Х, должны быть равны запросам потребителей:

Это означает, что запросы потребителей удовлетворяются полностью.

3) Необходимо также учитывать, что перевозки не могут быть отрицательными:

.

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

Формирование линий движения судов

Из портов А, Б, Е за навигацию необходимо отправить соответственно 611 тыс. тонн, 452 тыс. тонн, 766 тыс. тонн груза. В пункты назначения Л, М, Н, П, Р необходимо доставить соответственно 349 тыс. тонн, 197 тыс. тонн, 661 тыс. тонн, 90 тыс.тонн, 583 тыс. тонн груза.

Введем переменные в матрицу перевозок:

Построим матрицу расстояний:

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

АЛ = АБ + БВ + ВК + КЛ = 381+491+83+76 = 1031 км,

АМ = АБ + БВ + ВК + КМ = 381+491+83+327 = 1282 км,

АН = АБ + БВ + ВК +КЛ + ЛН = 381+491+83+76+75 = 1106 км,

АП = АБ + БВ + ВК +КЛ + ЛП = 381+491+83+76+392 = 1423 км,

АР = АБ + БВ + ВК +КЛ + ЛП + ПР = 381+491+83+76+392+220 = 1643 км,

БЛ = БВ + ВК + КЛ = 491+83+76 = 650 км,

БМ = БВ + ВК + КМ = 491+83+327 = 901 км,

БН = БВ + ВК +КЛ + ЛН = 491+83+76+75 = 725 км,

БП = БВ + ВК +КЛ + ЛП = 491+83+76+392 = 1042 км,

БР = БВ + ВК +КЛ + ЛП + ПР = 491+83+76+392+220 = 1262 км,

ЕЛ = ЕН + НЛ = 473+75 = 548 км,

ЕМ = ЕН +НЛ + ЛК + КМ = 473+75+76+327 = 951 км,

ЕН = ЕН = 473 км,

ЕП = ЕН + НЛ + ЛП = 473+75+392 = 940 км,

ЕР = ЕН + НЛ + ЛП + ПР = 473+75+392+220 = 1160 км,

Сначала необходимо проверить является ли данная задача с правильным балансом. Суммарное количество запасов груза в пунктах отправления должно равняться суммарному количеству запрошенного груза в пунктах назначения:

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

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

Исходные данные можно оформить в виде следующей таблице:

Таблица 2.1 – Исходные данные о запасах и запросах груза

ПН ПО	Л 349	М 197	Н 661	П 90	Р 583
А 611	1031	1282	1106	1423	1643	611
Б 452	650	901	725	1042	1262	452
Е 766	548	951	473	940	1160	766
Ф 51	0	0	0	0	0	51
	349	197	661	90	583

Строим первый опорный план методом Минимальных расстояний.

Таблица 2.2 – Первый опорный план

ПО   ПН	Л 349	М 197	Н 661	П 90	Р 583
А 611	1031	1282	1106	1423 79	1643 532	611
Б 452	650 244	901 197	725	1042 11	1262	452
Е 766	548 105	951	473 661	940	1160	766
Ф 51	0	0	0	0	0 51	51
	349	197	661	90	583

Считаем себестоимость данного плана по формуле 2.1:

Данная функция, определяющая грузооборот, должна достигать минимального значения.

Проверяя оптимальность данного плана, используют метод потенциалов.

Вводим потенциалы, т.е. платежи:

£_i – платеж поставщика,

– платеж за перевозку единицы груза потребителя,

 – псевдостоимость, которая определяется по формуле:

=£_i+                                           (2.2)

План считается оптимальным, когда выполняется следующее условие:

Для расчета псевдостоимости проверим количество базисных клеток по формуле:

R = m+n-1                                        (2.3)

где R – количество базисных клеток,

m – количество строк с перевозками,

n – количество столбцов с перевозками.

R = 4+5-1 = 8 – базисных клеток, значит можно дальше заполнять новую таблицу по следующим принципам:

1) Заменяем запасы груза на платежи поставщиков, а количество запрошенного груза на платежи за единицу груза потребителя.

2) В базисных клетках псевдостоимость равна стоимости.

3) £_А всегда равно нулю.

4) Рассчитываем остальные платежи и псевдостоимости (по формуле 2.2).

Таблица 2.3 – Проверка оптимальности полученного плана

ПО   ПН	Л 349	М 197	Н 661	П 90	Р 583	£i
А 611	1031  1031	1282  1282	956    1106	1423  1423 79	1643  1643 532	0
Б 452	650      650 244	901      901 197	575      725	1042  1042 11	1262  1262	-381
Е 766	548      548 105	799      951	473     473 661	940      940	1160  1160	-483
Ф 51	-612        0	-361        0	-687        0	-220        0	0              0 51	-1643
	1031	1282	956	1423	1643

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

Таблица 2.4 – План перевозок (тыс. тонн)

Себестоимость данного плана равна 1704,24 тыс. руб. Не хватает 51 тыс. тонн груза, поэтому необходимо искать дополнительного поставщика.