Решение транспортной задачи линейного программирования в среде MS Excel (стр. 5 из 9)
Следует заметить, что первые два этапа метода потенциалов является подготовительными. Все последующие действия имеют итеративный повторяющийся характер и выполняются в рамках построенной исходной таблицы.
3. Для построенной таблицы 2 находятся значения потенциалов пунктов производства и потребления: v1, v2,… vn, u1,u2,…um. С этой целью составляется и решается следующая система линейных уравнений:
(2.10)где индексы i и j соответствуют только ненулевым значениям переменных xij или занятым ячейкам таблицы 2.2. Как не трудно заметить, существование решения системы уравнений (2.10) обеспечивает выполнение второй группы условий критерия оптимальности (2.9). Для удобства найденные значения записываются в таблицу 2.2.
4. Для найденного решения системы уравнений (2.1) проверяется первая группа условий (2.8) критерия оптимальности. С этой целью вначале рассчитываются оценки свободных ячеек таблицы 2 по следующей формуле:
(2.11)где индексы i и j соответствуют только нулевым значениям переменных xij или занятым ячейкам таблицы 2.2. В этом случае проверка первой группы условий критерия оптимальности найденного решения сводится к проверке следующего условия только для ячеек:
(2.12)Если условие (2.12) выполняется, то найденное решения является оптимальным, и на этом дальнейшие расчеты могут быть завершены. Если же условие (2.12) не выполняется, то следует перейти к выполнению следующего этапа алгоритма метода потенциалов.
Из всех
выбирается наименьшее значение (если их несколько- то любое из них). Соответствующая свободная ячейка помечается знаком (+), и для нее в таблице метода потенциалов строится цикл. При этом циклом в таблице метода потенциалов называется ломаная, вершины которой расположены в занятых ячейках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. При правильном построении таблицы допустимого решение для любой свободной ячейки можно построить лишь один цикл.5. После того как построен цикл для выбранной свободной ячейки, следует рассчитать значения переменных нового допустимого решения. Для этого необходимо изменить значение переменных предыдущего допустимого решения в пределах ячеек, связанных с данной свободной ячейкой. Это изменение производят по следующим правилам:
· каждой ячейки, принадлежащей построенному циклу от выбранной свободной ячейки, приписывают определенный знак, причем свободной клетке – знак (+), а всем остальным клеткам – поочередно (+) и (-). Соответствующие ячейки называют также минусовыми и плюсовыми;
· в выбранную свободную ячейку записывают меньшее из чисел хij, стоящих в минусовых ячейках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых ячейках, и вычитают из чисел, стоящих в минусовых ячейках таблицы. При этом ячейка, которая ранее была свободной, становится занятой, а минусовая ячейка, в которой стояло минимальное из чисел хij , считается свободной.
В результате указанного изменения значений переменных в пределах ячеек, связанных циклом с данной свободной ячейкой, находится новое допустимое решение транспортной задачи, которому соответствует меньшее по сравнению с предыдущим решением значение целевой функции. После получения новой таблицы метода потенциалов следует прейти к выполнению действий этапа 3 настоящего алгоритма.
Рассмотренный алгоритм метода потенциалов может быть изображен графически в форме диаграммы деятельности языка UML.
В заключении следует отметить, что при определении начального допустимого решения или в процессе решения задачи может быть получено вырожденное решение. Чтобы избежать в этом случае зацикливания алгоритма, следует соответствующие нулевые элементы допустимого решения заменить сколь угодно малым положительным числом ε, после чего решать задачу как невырожденную. В оптимальном решении такой задачи необходимо считать ε равным нулю.
Для нахождения исходного допустимого решения транспортной задачи на этапе 2 алгоритма может быть использован так называемый метод минимального элемента. Сущность этого метода состоит в том, что начальное допустимое решение находится за п+т-1 шагов. При этом на каждом шаге находится значение только одной переменной хij, которая записывается в соответствующую ячейку. После чего данная ячейка становится занятой. Первоначально все ячейки таблицы свободные и среди них отыскивается такая ячейка, которой соответствует минимальное значение из коэффициентов целевой функции сij .Если таких ячеек несколько, то следует выбрать любую из них. Для найденной свободной ячейки определяется значение соответствующей переменной: хij = min{ai , bj}.
Заполнение выбранной ячейки обеспечивает полностью либо удовлетворение потребности в пункте потребления, если хij = bj = min{ai , bj }, либо вывоз всех запасов из пункта производства, если хij = ai = min{ai , bj}.
В первом случае исключают из дальнейшего рассмотрения столбец таблицы, соответствующий bj , а для i-й строчки полагают новое значение .Во втором случае исключают из дальнейшего рассмотрения строку соответствующую ai, а для j-го столбца полагают новое значение .
После исключения строки или столбца из дальнейшего рассмотрения происходит нахождение среди свободных ячеек следующего минимального значения сij и заполнение найденной ячейки очередным значением переменной: хij = min{ai , bj } с соответствующим исключением строки или столбца. В итоге после п+т-1 шагов метод минимального элемента позволяет получить начальное допустимое решение закрытой транспортной задачи линейного программирования.
Проиллюстрируем использование рассмотренного алгоритма метода потенциалов для решения индивидуальной транспортной задачи (2.6) и (2.7). Поскольку исходная задача является закрытой, то выполнение действий этапа 1 рассмотренного алгоритма метода потенциалов не требуется.
Исходная таблица метода потенциалов, необходимая для нахождения начального допустимого решения задачи (2.5) и (2.7), будет иметь следующий вид таблица 2.3.
Для нахождения начального допустимого решения воспользуемся методом минимального элемента. Для этого в таблице 2.3 следует найти минимальное значение сij , которое равно 1. этому значению соответствует второй пункт производства и первый пункт потребления, при этом х21 = min{a2 , b1 }=14. Из дальнейшего рассмотрения следует исключить второй пункт производства, а для первого пункта потребления определить новое значение b’=b1-a1=15-14=1.
Таблица 2.3. Исходная таблица для нахождения
начального допустимого решения
| F(x) | V1 15 | V2 12 | V3 8,5 | V4 5,5 |
| u1 10 | 3 | 5 | 7 | 11 |
| u2 14 | 1 | 4 | 6 | 3 |
| u3 17 | 5 | 8 | 12 | 7 |
На следующем шаге метода минимального элемента в сокращенной таблице таблица 2.3 найдем минимальное значение сij , которое равно 3. Этому значению соответствует первый пункт производства и первый пункт потребления, при этом х11 = min{a1 , b1 }=1. Из дальнейшего рассмотрения следует исключить первый пункт потребления, а для первого пункта производства определить новое значение a’=a1-b1=10-1=9.
Поступая аналогичным образом, в результате будет получено начальное допустимое решение транспортной задачи (2.6) и (2.7), исходная таблица метода потенциалов которой будет иметь следующий вид таблица 2.4.
Таблица 2.4. Исходная таблица метода потенциалов
с начальным допустимым решением
| F(x) | V1 15 | V2 12 | V3 8,5 | V4 5,5 |
| u1 10 | 3 1 | 5 9 | 7 | 11 |
| u2 14 | 1 14 | 4 | 6 | 3 |
| U3 17 | 5 | 8 3 | 12 8,5 | 7 5,5 |
Непосредственной проверкой можно убедиться, что найденное начальное решение действительно является допустимым. Этому начальному решению соответствует значение целевой функции:
F(x)=3*1+1*14+5*9+8*3+12*8,5+7*5,5=226,5
После выполнения подготовительных этапов 1 и 2 метода потенциалов можно приступить к проверке условия получения оптимального решения (этап 3). Для этого необходимо найти потенциалы пунктов производства и потребления. Поскольку число заполненных ячеек исходной таблицы равно п+т-1=6, то искомая система должна содержать п+т=7 неизвестных для 6 уравнений. А именно, для определения значений потенциалов следует решить следующую систему уравнений: {v1+u1=3, v1+u2=1, v2+u1=5, v2+u3=8, v3+u3=12, v4+u3=7}, содержащую шесть уравнений с семью неизвестными. Поскольку число неизвестных превышает на единицу число уравнений, то одно из неизвестных можно положить равным произвольному числу, например v1=0. Далее можно найти последовательно из данной системы уравнений значения остальных неизвестных: v2=2, v3=6, v4=1, u1=3, u1=2, u3=6.