Курс лекций по линейному программированию (стр. 3 из 6)
Через конечное число шагов данный метод приводит к новой задаче, оптимальное решение которой является оптимальным целочисленным решением.
Пусть а- действительное число. Число [a] – целая часть числа а – это наибольшее целое, не превосходящее данного числа.
qa- дробная часть числа – это разность между числом и его целой частью а-[a] 0≤qa<1
основой метода является понятие правильного отсечения. Пусть х* - оптимальный план ослабленной задачи, который не является целочисленным. Неравенство αх≤β называется правильным отсечением или отсечением Гомори, если оно удовлетворяет условиям:
1. условие отсечения. Если х* оптимальный не целочисленный план, то он не удовлетворяет этому ограничению αх*>β
2. условие правильности. Для любого целочисленного плана х* αх*≤β
3. необходимое условие применения аддитивного компонента является целочисленность в системе ограничений элементов правых частей. Оно не выполняется если иррациональное или трансцендентное.
Алгоритм:
1. решается ослабленная задача. Если оптимальный план целочисленный , то он является решением целочисленной задачи, иначе переходим к шагу 2.
2. вводятся дополнительные линейные ограничения – правильное отсечение. Переходим к шагу 1, решая ослабленную задачу с дополнительными ограничениями.
Условие неразрешимости целочисленной задачи.
Задача не разрешима, если для дробного значения переменной задачи хj все коэффициенты аij в данной строке симплекс – таблицы оптимального решения ослабленной задачи окажутся целыми.
Схема алгоритма.
Пусть при решении задачи получился оптимальный план, имеющий хотя бы 1 нецелочисленную компоненту, тогда в симплекс – таблице оптимального решения выбираются значения базисной переменной задачи в наибольшей дробной частью. Если таких переменных несколько, то выбирается любая.
Этой переменной соответствует строка таблицы, называемая строкой производящей отсечение. Выписывается уравнение:
Т.к. коэффициенты целевой функции – целые числа, то значения целевой функции на целочисленном решении тоже должно быть целым. Представим каждый коэффициент строки в виде суммы целых и дробных частей, получим:
хj* = [xj*] + qj 0<qj<1
aij = [aij] + qij 0≤qij<1
переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой.
xj – [xj] + ∑[qij]xj=qj+∑qijxj
т.к. переменные xm+1, … , xn, принимают целочисленные значения, то правая часть уравнения является целочисленной, следовательно, в силу не отрицательности дробных частей и переменных задачи, получаем:
qi+∑aijxj≥0, => qi-∑aijxj≤qj,
т.к. qj<1, то заменяем в правой части qj на 1 и получает неравенство qi-∑aijxj≤1
т.к. левая часть неравенства должна принимать целые значения, то необходимое условие её целочисленности записывается в виде:
qi-∑qij<1
Вводя остаточною переменную Sj получим выражение для переменной Гомори Sj.
qj-∑qijxj+Sj=0,
где Sj – неотрицательная добавочная переменная, которая по определению должна принимать целое значение, но для данной системы ограничений =>, что если
xj=0, то Sj=-qj,
т.е. она принимает отрицательное значение => не является допустимой. Т.о. полученное ранее решение не удовлетворяет новому ограничению и в этой ситуации используется М-метод.
2.Комбинаторный метод
Идеи: Пусть решение задачи без ограничений целочисленности х* - целочисленная переменная, значение которой в оптимальном плане является дробным, то интервал
{x*]≤xr<[xr*]+1 не содержит допустимых решений с целочисленной координатой хr => допустимое значение хr должно удовлетворять одному из следующих неравенств:
хr≤[xr*],
xr≥[xr*]+1
Введение этих условий в задаче порождает 2 несвязанные между собой задачи с одной и той же целевой функцией, но е пересекающимися областями дополнительных решений. В этом случае говорят, что задача разветвляется.
Осуществленный в процессе ветвления учет необходимых условий целочисленности позволяет исключить часть многогранника дополнительных решений не содержащих точек с целыми координатами.
Решаем каждую из координат если полученный оптимум окажется допустимым и для целочисленной задачи, то его значение фиксируется как наилучшее, при этом нет необходимости продолжать ветвление каждой из подзадач. Иначе подзадача разбивается на 2 подзадачи при учете условий целочисленности значений, которые в оптимальном плане не оказались целыми.
Как только полученное целочисленное решение одной их подзадач окажется лучше имеющегося, то оно фиксируется вместо зафиксированного ранее.
Процесс ветвления продолжается до тех пор, пока какая-либо из подзадач не приведет к целочисленному решению или пока не будет установлена невозможность его существования.
Для эффективности вводятся понятия, на основании которых делается вывод о необходимости разбиения каждой из подзадач.
Если оптимальное решение подзадачи обеспечивает худшее значение целевой функции, чем имеющееся ранее, то подзадачу не рассматривают, говорят, что она прозондирована и ее исключают из списка исходных задач.
Содержательно, как только получено допустимое значение, то соответствующее значение целевой функции может быть использовано в качестве верхней (в случае минимума) и нижней (в случае максимума) границы, наличие которой позволяет формализовать процедуру исключения прозондированной задачи.
Лекция № 4: «Транспортная задача».
Пусть имеется m пунктов производства (складирования) однородной продукции, запасы которой = А1, … , Аn. Имеется n пунктов потребления этого же продукта с потребностями В1, … , Вn; известны тарифы (транспортные расходы, связанные с доставкой единицей продукта из заданного пункта отправления в пункт потребления. {Cij} i=
j= 
/Требуется составить план перевозок (какое количество, из какого пункта отправления в какой пункт назначения надо везти), обеспечивающий наиболее экономичным путем при суммарных минимальных затратах, удовлетворяющий спрос всех пунктов потребления за счет реализации всего продукта, находящегося в пункте отправления.
Формально требуется указать вектор х={xij} поставок (хij≥0 – ограничения, где хij количество единиц продукта, направленный из i-ого пункта отправления в j-ый пункт назначения), который удовлетворяет следующим условиям:
1. условие полного удовлетворения потребления для всех пунктов потребления
2. Весь продукт, хранимый в пункте отправления должен быть вывезен ∑хij=Ai
3. достовляющ. минимум целевой функции
транспортная задача исследуется только на минимум.
ТЗ называется закрытой (сбалансированной), если выполняется условие:
В противном случае ТЗ называется открытой.
Теорема: необходимое условие разрешимости ТЗ.
ТЗ разрешима тогда и только тогда, когда она сбалансирована. Если задача открыта, то для преобразования её в закрытую следует сделать:
а.) в случае дефицита (суммарное потребление > суммарных запасов) вводится пункт потребления с запасами равными
Из которого перевозку во все пункты назначения осуществляют по нулевым тарифам
б.) в случае избытка продукции вводится фиктивный пункт потребления с потреблением равным:
в который перевозки осуществляются по нулевым тарифам.Метод решения ТЗ.
Пусть имеется ТЗ:
хij≥0
Общее число уравнений m+n.
Это каноническая форма линейной задачи, но т.к. присутствует условие сбалансированности
Которое «связывает» некоторые из этих m+n уравнений, то число линейных независимых уравнений (переменных) = n+m-1. Т.к. известны в задаче т. n, то в невырожденном опорном плане должно быть n+m-1 положительная компонента с остальными нулевыми.
Содержательно: имеем n+m-1 ненулевую поставку, которые образуют суммарный объем перевозок из всех пунктов отправления во все пункты потребления.