Методы оптимизации

.

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

, i=1,2,…,m.

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

, j=1, 2, … , n.

Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:

, (1)

, i=1,2,…,m , (2)

, j=1, 2, … , n, (3)

, i=1,2,,…,m, j=1,2,…,n (4)

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

.

Такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой.

Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).

Свойство системы ограничений транспортной задачи.

Теорема Ранг системы - условий транспортной задачи равен N=m+n-1.

5.3Опорное решение транспортной задачи

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равно m+n-1,а для вырожденного опорного решения меньше m+n-1

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

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

Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена ломаной линии на 900. Простейшие циклы изображены на рис1, где звездочкой отмечены клетки таблицы, включенные в состав цикла.

5.4Методы построения начального опорного решения

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

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

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

1. если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj, ;

2. если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki, ;

3. если , то и исключается либо i-й поставщик,

, k=1, 2, …, n, kj, , либо j-й потребитель, ,

k=1, 2, …, m, ki, .

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

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы.

Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому опорное решение, построенное данным методом, может быть далеко от оптимального.

Метод минимальной стоимости.

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,…,m, j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.

Переход от одного опорного решения к другому.

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

Метод потенциалов.

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений - нахождение оценок свободных клеток.

Теорема. (признак оптимальности опорного решения). Если допустимое решение Х=(), i=1,2,,…,m, j=1,2,…,n транспортной задачи является оптимальным, то существует потенциалы (числа) поставщиков , i=1,2,,…,m и потребителей , j=1,2,…,n, удовлетворяющие следующим условиям:

+= при >0, (12)

+ при =0. (13)

Группа равенств (12) += при >0 используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например -+= или -=, если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

Данная система уравнений имеет m+n неизвестных , i=1,2,,…,m и , j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

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

Оценки для свободных клеток транспортной таблицы используются для улучшения опорного решения. С этой целью находят клетку (k, l) таблицы, соответствующую max{}=. Если 0, то решение оптимальное. Если же >0, то для соответствующей клетки (k, l) строят цикл и улучшают решение, перераспределяя груз = по этому циклу

5.5Практическая часть

Условия задачи: Пусть некоторый однородный продукт сосредоточен у 3 поставщиков. Назовем их Количество единиц продукции каждого поставщика соответственно равно140, 120, 60. Данную продукцию необходимо доставить 4 потребителям в количестве 90, 80, 60, 90. Известна стоимость перевозки единицы груза от i-ого поставщика к j-ому потребителю

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

Математическая модель задачи

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

=320. Следовательно, модель является закрытой.

Решение поставленной задачи