Транспонирование матрицы переход от матрицы А к матрице А', в которой строки и столбцы поменялись местами с сохранением порядка. Матрица А' называется транспонированной относительно матрицы А:
Требуется найти максимум функции f(xi,x 2,...,x n ) при условиях Здесь f, g i функции, x 1, x 2, · · ·, x n параметры управления. Выражение f(xi,x 2,...,x n ) называется функцией цели. Условия представляют собой ограничения поставленной задачи.
транспортная задача определение оптимального плана перевозок груза из m пунктов отправления A1, A2,..., Am в n пунктов назначения B1, B2,..., Bn. определение минимального значения целевой функции стоимости перевозок Всякое неотрицательное решение систем линейных уравнений, называется планом транспортной задачи. План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
транспортная задача Пункты отправлени я Пункты назначения Запас ы B1B1...BjBj BnBn A1A1 c 11 x c 1j x 1j... c 1n x 1n a1a1... AiAi c i1 x i1... c ij x ij... c in x in aiai... AmAm c m1 x m1... c mj x mj... c mn x mn amam Потребност и b1b1...bjbj bnbn Сij тарифы перевозок Xij количество груза
Определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. опорный план находят последовательно за n+m-1 шагов, на каждом из которых в таблице условий задачи заполняют одну клетку, которую называют занятой. заполнение одной из клеток обеспечивает полностью либо удовлетворение потребности в грузе одного из пунктов назначения, либо вывоз груза из одного из пунктов отправления. Опорный план является исходным условием для проверки последнего на оптимальность и нахождения оптимального плана.
Прямая и двойственная задачи линейного программирования. Определить максимальное значение функции F=c 1 x 1 +c 2 x c n x n при условиях Определить минимальное значение функции F * =b 1 y 1 +b 2 y b n y n при условиях Эти задачи образуют пару задач, называемую двойственной парой.
двойственная задача по отношению к исходной составляется согласно следующим правилам: 1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной - на минимум. 2. Матрица составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица в двойственной задаче получаются друг из друга транспонированием. 3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче. 4. Коэффициентами при неизвестных в целевой функции двойственной являются свободные члены в системе условий исходной задачи, а правыми частями в ограничениях системы условий двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи. 5. Если переменная x j исходной задачи может принимать только лишь неотрицательные значения, то j-е ограничение в системе условий двойственной задачи является неравенством вида >=. Если же переменная x j может принимать как положительные, так и отрицательные значения, то j-е ограничение в системе условий двойственной задачи представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i-е ограничение в системе условий исходной задачи является неравенством, то i-я переменная двойственной задачи y i >=0. Если же i-е ограничение есть уравнение, то переменная y i может принимать как положительные, так и отрицательные значения. Двойственные пары задач обычно подразделяются на симметричные и несимметричные. В симметричной паре двойственных задач ограничения прямой задачи и ограничения двойственной задачи являются соответственно неравенствами вида =. Таким образом, переменные обоих задач могут принимать только лишь неотрицательные значения.
при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи. Лемма 1. Если X - некоторый план исходной задачи, а Y - произвольный план двойственной задачи, то значение целевой функции исходной задачи на плане X всегда не превосходит значение целевой функции двойственной задачи на плане Y, т.е. F(X)
Теорема 1. (первая теорема двойственности). Если одна из пары двойственных задач прямая или обратная имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой т.е. Fmax=F*min. Если целевая функция одной из пары двойственных задач не ограничена (Для исходной задачи – сверху, для двойственной – снизу), то другая задача вообще не имеет планов. Теорема 2. (вторая теорема двойственности). План X*=(x1*,x2*, …, xn*) исходной задачи и план Y*=(y1*, y2*, …, yn*) двойственной задачи являются оптимальными планами этих задач тогда и только тогда, когда для любого j (j=1,n) выполняется равенство
Метод потенциалов - находят опорный план транспортной задачи, - его последовательно улучшают до получения оптимального плана. Теорема Если для некоторого опорного плана X * =(x ij * ) (i=1,m; j=1,n) ТЗ существуют такие числа α 1, α 2,..., α m, β 1, β 2,..., β n, что β j - α i =c ij при x ij >0 β j - α i
Метод потенциалов алгоритм нахождения решения транспортной задачи. Пусть одним из рассмотренных выше методов найдет опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяются потенциалы α i и β j (i=1,m; j=1,n). Эти числа находят из системы уравнений β j - α i =c ij где c ij - тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи. число заполненных клеток равно m+n-1 система с m+n неизвестными содержит m+n-1 уравнений одно из неизвестных можно положить равным произвольному числу, например α 1 =0, найти последовательно из уравнений значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа a ij =β j - α i -c ij.
Метод потенциалов алгоритм нахождения решения транспортной задачи. Если среди чисел a ij (i=1,m; j=1,n) нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки a ij >0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых a ij >0, и среди данных чисел выбирают максимальное. Клетку, которой соответствует это число, следует заполнить. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполняемой клеткой так называемым циклом.
Циклом в таблице условий транспортной задачи называется ломанная линия, вершины которой расположены в занятых клетках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое в столбце. Если ломанная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл.
После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных циклом с данной свободной клеткой. Это перемещение производят по следующим правилам: 1)каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке - знак плюс, а всем остальным клеткам - поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми); 2) в данную свободную клетку переносят меньшее из чисел x ij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становиться занятой, а минусовая клетка, в которой стояло минимальное из чисел x ij, считается свободной.
В результате указанных выше перемещений грузов в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи. Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно остается равным m+n-1. в минусовых клетках имеется два (или более) одинаковых числа x ij, то освобождается лишь одну из таких клеток, а остальные остаются занятыми (с нулевыми поставками). Полученный новый опорный план транспортной задачи проверяют на оптимальность. определяют потенциалы пунктов отправления и назначения и находят числа a ij =β j -α i -c ij для всех свободных клеток. Если среди этих чисел не окажется положительных, то это свидетельствует о получении оптимального плана. Если же положительные числа имеются, то следует перейти к новому опорному плану. В результате итерационного процесса после конечного числа шагов получают оптимальный план задачи.
Решение транспортной задачи методом потенциалов Найденный в предыдущих примерах опорный план проверяем на оптимальность. находим потенциалы пунктов отправления и назначения. Для определения потенциалов получаем систему содержащую шесть уравнений с семью неизвестными: β1- α1=1, β2- α1=2, β2- α2=3, β3- α2=1, β4- α2=5, β4- α3=4,
Решение транспортной задачи методом потенциалов Полагая α1=0, находим β1=1, β2=2, α2=-1, β3=0, β4=4, α3=0. Для каждой свободной клетки вычисляем число aij=βj-αi-cij: a13=-4, a14=3 a21=a32=0, a31=-2, a33=-4. Заключаем найденные числа в рамки и записываем их в каждую из свободных клеток таблицы.
Так как среди чисел aij имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Наибольшим среди положительных чисел aij является a14=3, поэтому для данной свободной клетки строим цилк пересчета и производим сдвиг по этому циклу. Наименьшее из чисел в минусовых клетках равно 10.
Клетка, в которой находится это число, становится свободной в новой таблице. Другие числа в табл. получаются так: к числу 10, стоящему в плюсовой клетке табл… добавим 10 и вычтем 10 из числа 20, находящегося в минусовой клетке ….. Клетка на пересечении строки A2 и столбца B2 становится свободной.
Наименьшее из чисел в минусовых клетках равно 10. Клетка, в которой находится это число, становится свободной в новой таблице. Другие числа в табл. получаются так: к числу 10, стоящему в плюсовой клетке табл… добавим 10 и вычтем 10 из числа 20, находящегося в минусовой клетке ….. Клетка на пересечении строки A2 и столбца B2 становится свободной.
После этих преобразований получаем новый опорный план.
Этот план проверяем на оптимальность, Снова находим потенциалы пунктов отправления и назначения. Для этого составляем следующую систему уравнений: β1-α1=1, β2-α1=2, β2-α2=3, β3-α2=1, β4-α1=1, β4-α3=4.
Полагая α1=0, находим β1=β4=1, β2=2, α2= -1, β3=0, α3= -3. Для каждой свободной клетки вычисляем число aij: a13= -2, a21= 0, a24= -3, a31=1, a32=3, a33=-1. данный план перевозок не является оптимальным.
переходим к новому опорному плану.
Полученный опорный план оптимальный, поскольку, все числа aij