Метод Гомори. (Идея, геометрическая интерпретация, алгоритм)

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

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

• любое целочисленное решение исходной зада­чи ему удовлетворяет;
• любое нецелочисленное решение исходной задачи ему не удовлетворяет.

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

Пусть задача линейного программирования решена симплекс-методом и ее оптимальное решение не удовлетворяет условиям целочисленности. Тогда составляется дополнительное ограничение. Дополнительное ограничение записывается в виде

где дробные части чисел (a_ij) и (b_i).

Решение задач целочисленного программирования выполняется в следующем порядке:

• решается исходная задача до получения оптимального решения;
• если оптимальное решение целочисленно, то процесс заканчивается, если условия целочисленности не выполняются, то переходят к следующему пункту;
• на основании последней симплекс-таблицы оптимального плана для базисной пе­ременной, имеющей наибольшую дробную часть, строится сечение;
• добавление сечения (ограничения) к условиям оптимального не­целочисленного плана приводит к образованию расширенной зада­чи, после чего возвращаются к п. 1.

Рассмотрим пример: найти хотя бы одно оптимальное целочисленное решение задачи

Для решения можно использовать двойственный симплекс-метод.Условия задачи представлены в виде таблицы модифицирован­ных жордановых исключений (табл. 4.1).

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

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

В f - строке условие критерия выполняется. Однако полученный план недопустимый. В столбце свободных членов все элементы от­рицательны. Проделав две операции симплексных преобразований, получим оптимальное, по нецелочисленное решение/

Значение целевой функции для плана x*₁ = (1/2; 0; 4/3; 1/6; 0; 0) равно f₁min = 11/6.

Строим дополнительное ограничение. Наибольшую дробную часть имеет базисная переменная

Вводим дополнительное ограничение. Тогда таблица примет следующий вид.

БП		СП
-x5 -x2 -x6
x4= x1= x3= x7=	1/6 1/2 4/3 -1/2	-1/2 5/6 -2/3 -1/2 1/2 0 0 2/3 -1/3 -1/2 -1/2 0
f =		-1/2 -5/6 -1/3

БП		СП
-x7 -x2 -x6
x4= x1= x3= x5= x8=	-2/3 4/3 -2/3	-1 4/4 -2/3 -1 1 0 0 2/3 -1/3 -2 1 0 0 -1/3 -1/3
f =	7/3	-1 -1/3 -1/3

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

К базисной переменной x₄, имеющей наибольшую дробную часть, составим дополнительное ограничение. С этой целью в табл. 4.4 предварительно оставляем место для новой базисной дополнитель­ной переменной x₈. Для этого необходимо от свободного члена и коэффициентов при свободных базисных переменных x₇, х₂ и х₆ взять дробную часть и записать ее в соответствующем столбце с противоположным знаком.

Проделав симплексные преобразования с разрешающим элемен­том —1/3, выделенным в табл, получим новый уже полностью целочисленный план. Для оптимального целочисленного плана х* = (1; 0; 2; 2; 1; 2; 0; 0) значение целевой функции f _min=3.

Метод решения поставленной задачи – метод Гомори, который основан на симплексном методе. Симплексным методом находится оптимальный план задачи без учета целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают. Если же оптимальный план содержит хотя бы одну дробную компоненту x_i, то накладывают дополнительное ограничение, учитывающее целочисленность .

Геометрический смысл дополнительного ограничения: пусть в точке А многогранника решений Q функция Z достигает максимального значения Z(A) = max, но координаты точки А – дробные. Тогда введеные ограничения по целочисленности 1 и 2 от области Q отсекают область Q^/ с угловой точкой A^/, координаты которой целочисленные и в которой линейная функция достигает максимального значения.

1. Транспортная задача. Метод потенциалов.

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А₁,..., А_m, в которых сосредоточены запасы однородных продуктов в количестве a_i,...,а_m единиц. Имеется n пунктов назначения (или пунктов потребления) B₁,...,В_m, потребность которых в указанных продуктах составляет b₁,...,b_n единиц. Известны также транспортные расходы C_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт B_j, i — 1,..., m; j = 1,...,n. Предположим, что

, т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть х_ij - количество единиц продукта, поставляемого из пункта A_i в пункт B_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что i=1,…,m.

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

j=1,…,n.

Объемы перевозок - неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены: xij≥0, i=1,…,m; j=1,…,n.

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

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

i=1,…,m.

Введение этого условия приводит к открытой транспортной модели.

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

Как одна из задач линейного программирования транспортная задача принципиально может быть решена универсальным методом решения любой задачи линейного программирования, но этот метод не учитывает

специфики условий транспортной задачи. Поэтому решение ее симплекс-методом оказывается слишком громоздким.

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

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам А_i соответствуют числа u_i, пунктам В_j - числа V_j. Они выбираются таким образом, чтобы их разность на k-й итерации была равна C_ij - стоимости перевозки единицы продукции между пунктами А_i и B_j:

V_j[k] - u_i[k] = C_ij, i=1,...,m; j = 1,...,n.

Если разность предварительных потенциалов для каждой пары пунктов A_i, B_j не превосходит C_ij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.

1. Транспортная задача на сети.

При построении опорного плана соблюдаются следующие условия:

• Все запасы должны быть распределены, а потребности удовлетворены;
• К каждой вершине сети должна подходить или выходить из нее хотя бы одна стрелка;
• Общее число стрелок должно быть на единицу меньше числа вершин;
• Стрелки не должны образовывать замкнутый цикл.

Рассмотрим следующий пример:

- поставщики; - - потребители

(+) - наличие груза; (-) - потребности

20 25

нарушение 22 5 30

нарушение 31

+35 25 20 -10 15 65 (-16)

34 8 40

30 35

100 70 105

(-34) (+42) (-23)

1) Первый потенциал берем произвольно (!!! В нашем примере берем 100!!!, он находиться у первой вершины).

2) Если двигаемся против направления перевозки, то от потенциала отнимаем стоимость перевозки (т.е. 100 – 30 = 70, (см. у вершины № 7)), а если двигаемся по направлению перевозки, то к значению добавляем стоимость перевозки (т.е 70 + + + 35 = 105, (см. у вершины № 6)).

3) Для незанятых веток вычисляем разность потенциалов (нарушение) по модулю и минус стоимость перевозок: (!100 – 40! – 25 = +35) и (!70 – 60! – 20 = -10)

4) Выбираем максимальное положительное нарушение и загружаем эту ветку (красная стрелка от меньшего потенциала к большему).

5) Получили замкнутый цикл, который обходим в направлении красной стрелки и выбираем минимальную встречную перевозку (15).

21 25

нарушение 22 5 30

нарушение 31

+35 25 20 -10 15 65 (-16)

34 8 40

30 35 минимальная

100 70 105 встречная перевозка (15)

(-34) (+42) (-23)

6) К попутным перевозкам прибавляем найденное число (15), а от встречных отнимаем. При этом получаем улучшение плана: 35 · 15 = 525, где 35 – максимальное положительное нарушение, 15 – минимальная встречная перевозка, а 525 – на столько единиц улучшился план.

 

75 (+22) 95 (-27) 70 (+36)

22 25

7 20 30

16

25 15 20 +5 100 (-16)

19 23 40 -35

30 35

100 70 105

(-34) (+42) (-23)

Полученный план не является оптимальным.

7) Повторяем все действия аналогично, как и в предыдущих пунктах. Получаем оптимальный план.

нарушение

23 25

<0 20 30

16

25 22 20 7 95 (-16)

12 23 40

30 35 <0

100 70 105

(-34) (+42) (-23) нарушение

Положительного нарушения нет => план оптимальный.

f = 25·22 + 30·12 + 35·23 + 30·16 + 25·20 + 20·7 = 52835

1. Нелинейное программирование(НП). Трудности, порожденные нелинейностью. Графический метод решения задач нелинейного программирования.

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор X = (x₁,..., x_n), удовлетворяющий системе ограничений

g_i (x_1,..., x_n) = b_i i = 1... k

g_i (x_1,..., x_n) ≤ b_i i = k + 1,..., m

и доставляющий экстремум функции Z = f (x_1,..., x_n).

При этом предполагается, что известны функции g_i (x_1,..., x_n) и f (x_1,..., x_n). Обычно на некоторые переменные x_1,..., x_n накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных. Если

n

(1) g_i (x_1,..., x_n) = ∑ a_ijx_j i=1..m,

i=1

n

(2) Z = f (x_1,..., x_n) = ∑ C_jx_j,

j=1

где a_ij и C_j - известные константы, то при условии неотрицательности решения получаем задачу ЛП. Любую другую задачу математического программирования, не удовлетворяющую условиям (1) и (2), условимся считать нелинейной.

Класс задач нелинейного программирования шире класса задач ЛП. Подробное изучение практических задач, которые условились считать линейными, показывает, что они в действительности являются нелинейными. Возникает задача нахождения эффективных методов решения задач нелинейного программирования. Существующие методы позволяют решать узкий класс задач, ограничения которых имеют вид (1). Даже если область допустимых решений выпуклая, то в ряде задач целевая функция может иметь несколько локальных экстремумов. С помощью большинства же вычислительных методов можно найти точку локального оптимума, но нельзя установить, является она точкой глобального (абсолютного) оптимума или нет. Если в задачах ЛП точка экстремума является вершиной многогранника решений, то в задачах нелинейного программирования она может лежать в вершине многогранника, на ребре или внутренней области. Если задача содержит нелинейные ограничения, то область допустимых решений не является выпуклой и кроме глобального оптимума могут существовать точки локального оптимума.

Также как и в ЛП задачи нелинейного программирования могут быть решены графически.

Пример. Найти минимальное и максимальное значения сепарабельной функции Z = (x₁ - 4)² + (x₂ - 6)² при ограничениях:

x₁ + x₂ ≥1

2x₁ + 3x₂≤ 12

x₁≥0, x₂≥0.

Решение. Область допустимых решений представляет собой многоугольник ABCE. Если положить Z = Q (Q>0), то получим уравнение окружности (x₁ –4) + (x₂ - 6) = Q. С уменьшением (увеличением) Q (квадрата радиуса) значения функции Z соответственно уменьшаются (увеличиваются). Проводя из точки М, как из центра, окружности различных радиусов, получим: минимальное знач ение функция

Z(D) = 196/13 принимает в точке D (24/13; 36/13), в которой окружность касается области решений. Точка D не является угловой, ее координаты находят в результате решения системы уравнений, соответствующих прямым MD и CE. Функция Z имеет два локальных максимума: в вершине А(1;0) функция Z(A) = 45, в вершине E(6;0) функция Z(E) = 5, в вершине C(0;4) функция Z(C) = 25, причем глобальный максимум достигается в вершине С.

1. Классические методы оптимизации. Метод множителей Лагранжа.

Ограничение в виде уравнения

=b , i=

Z=f(X)

и f С (G)

Составляем функцию Лагранжа

L(x ,.., x , ,..., =f(x ,..., x +

Исследуем эту функцию на безусловный экстремум. Получаем систему из n+m уравнений. Находим частные производные.

Если целевая функция в точке X имеет экстремум, то существует такой вектор ), что (X является решением системы.

Ограничение в виде неравенства

f(X);

• Находим точку безусловного экстремума

и среди них выбираем, которые попали в ОДЗ

• Находим стационарные точки

• Находим точки min и max (как и при безусловном экстремуме).

Поиск по сайту: