Целочисленное программирование. Метод Гомори

Если на все или некоторые переменные наложено условие дискретности, например целочисленности ( ), то такие задачи рассматриваются в разделе математического программирования, называемого дискретным, в частности целочисленным,программированием.

Задача целочисленного линейного программирования записывается следующим образом:

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

Если оптимальный план целочисленный, то он и будет решением всей задачи.

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

,

где {a_ij}, {b_i} – дробные части чисел a_ij и b_i.

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

Задача не имеет целочисленного решения, если для дробного b_i все a_ij в этой строке целые.

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

,

где –целая часть числа.

Например,

;

;

.

Пример 9. Решить задачу

Решение

Решая задачу симплекс-методом, получим оптимальный план , в котором х₁ и х₂ – дробные (табл. 17).

Таблица 17

БП	сБ	А0		–1	–3
x1	x2	x3	x4	x5	x6
x3	–3
x2	–1
х1

Составим дополнительное ограничение для базисной переменной , имеющей наибольшую дробную часть:

Находим дробные части:

Тогда ограничение примет вид

Преобразуем это неравенство в уравнение

где x₇ ³ 0 и целое.

Введем искусственную базисную переменную x₈ ³ 0 и целую. получим

На основании табл. 17 составим табл. 18 расширенной задачи.

Таблица 18

БП	сБ	А0		–1	–3					М
x1	x2	x3	x4	x5	x6	x7	x8
х3	–3
x2	–1
х1
x8	М								–1
								–М

Решаем расширенную задачу симплекс-методом. План, записанный в табл. 18, не является оптимальным. Выберем разрешающий столбец: (например, шестой). Найдем , т. е. возьмем разрешающую, например, четвертую строку. Итак, разрешающим элементом является . Выполнив симплексные преобразования, придем к табл. 19.

Таблица 19

БП	сБ	А0		–1	–3
x1	x2	x3	x4	x5	x6	x7
x3	–3
x2	–1					–1
x1						–1
x6
	–15				–6

Полученный план (0; 3; 4; 0; 0; 1) является оптимальным и целочисленным, а f_min = –15.

Ответ: x₁ = 0; x₂ = 3; x₃ = 4; f_min = – 15.

Вопросы для самоконтроля

1. Постановка задач целочисленного линейного программирования: общей задачи о расписании; задачи коммивояжера; задач о разбиении, покрытии и упаковке; задачи о размещении оборудования; задачи раскроя.

2. Общая идея метода Гомори.

3. Алгоритм метода Гомори.

4. Суть метода ветвей и границ.

6. Нелинейное программирование.
Метод множителей Лагранжа

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

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

Метод Лагранжа активно используется для обоснования различных современных численных методов, широко применяемых на практике. Что же касается функции Лагранжа и множителей Лагранжа, то они играют самостоятельную и исключительно важную роль в теории и приложениях не только математического программирования.

Рассмотрим классическую задачу оптимизации

Функции и непрерывны и имеют частные производные, по крайней мере, второго порядка.

В простейшем случае условным экстремумом функции f(x₁; x₂) называется максимум или минимум этой функции, достигнутый при условии, что x₁ и x₂ удовлетворяют дополнительному условию (уравнению связи) φ(x₁; x₂) = b.

Условный экстремум функции f(x₁; x₂) при наличии дополнительного ограничения φ(x₁; x₂) = b находят с помощью так называемой функции Лагранжа

L(x₁; x₂; λ) = f(x₁; x₂) + λ · (b – φ(x₁; x₂)),

где λ – неотрицательный постоянный множитель (множитель Лагранжа).

Необходимое условие экстремума сводится к существованию решения системы трех уравнений с тремя неизвестными x₁, x₂, λ:

В результате решения системы находятся все стационарные точки функции Лагранжа.

Достаточное условие экстремума сводится к изучению знака второго дифференциала функции Лагранжа

Функция f(x₁; x₂) имеет в стационарной точке (x₁; x₂; l) условный максимум, если в ней d²L < 0, и условный минимум, если d²L > 0.

Аналогично находится условный экстремум функции трех и большего числа переменных. Заметим, что второй дифференциал d²L функции Лагранжа для трех переменных имеет вид

Можно указать следующий порядок решения классической задачи оптимизации методом множителей Лагранжа:

1. составить функцию Лагранжа

L(x₁; …; x_n; λ) = f(x₁; …; x_n) + λ · (b – φ(x₁; …; x_n)).

2. найти частные производные функции Лагранжа по всем переменным x₁, …, x_n,l и приравнять их к нулю. Тем самым будет получена система, состоящая из n + 1 уравнений. Решить полученную систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа.

3. из стационарных точек функции L, взятых без координаты l, выбрать точки, в которых функция f имеет условные экстремумы при наличии ограничения j(x₁; …; x_n) = b. Этот выбор осуществляется, например, с применением достаточного условия.

Пример 10. Найти условный экстремум функции f = 6 – 4x₁ – 3x₂, если

Решение

Задачу выполняем в следующем порядке:

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

2. Необходимые условия дают систему уравнений

Решая эту систему уравнений, находим

3. Так как то

Если то d²L > 0. значит, в точке функция f имеет условный минимум.

Если же то d²L < 0. значит, в точке функция f имеет условный максимум.

При этом f_max = 11, f_min = 1.

Ответ:

Вопросы для самоконтроля

1. Общая постановка задачи нелинейного программирования.

2. Суть метода Лагранжа, применяемого для решения классической оптимизационной задачи.

3. Составление функции Лагранжа.

4. Необходимое условие экстремума.

5. Достаточное условие экстремума.

6. Порядок решения классической задачи оптимизации методом множителей Лагранжа.

7. Метод динамического программирования.
Задача выбора кратчайшего пути

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

Пример 11. На сети дорог (рис. 11) указаны расстояния (в километрах) между промежуточными пунктами сети.

Рис. 11

Найти самый короткий маршрут из пункта 1 в пункт 10, составить таблицу оптимальных маршрутов из всех остальных пунктов сети в пункт 10 и указать кратчайшее расстояние от каждого пункта до пункта 10.

Решение

задаче необходимо придать шаговый характер. Разобьем все пункты сети на группы (табл. 20).

Таблица 20

Группы
1-я	2-я	3-я	4-я	5-я

К первой группе отнесем пункт 1; ко второй – пункты, в которые можно попасть непосредственно из пункта 1 (таковыми будут пункты 2, 3, 4); к третьей группе отнесем пункты, в которые можно попасть непосредственно из любого пункта второй группы (пункты 5, 6, 7) и т. д. В результате движение из пункта 1 в пункт 10 распадается на этапы.

На первом этапе необходимо из пункта 1 попасть в какой-нибудь пункт второй группы, на втором этапе – из пункта второй группы в пункт третьей группы и т. д.

В связи с этим маршрут из пункта 1 в пункт 10 разобьется на шаги. В данном случае этот процесс будет состоять из четырех шагов.

Будем оптимизировать каждый шаг, начиная с последнего, четвертого, при этом условные оптимальные шаговые решения пометим на сети стрелкой, выходящей из соответствующего кружка, а условный оптимальный эффект (в нашем случае это расстояние, которое следует преодолеть от данного пункта до пункта 10, двигаясь по оптимальному маршруту) запишем в нижнем кружке (рис. 12).

Рис. 12

На четвертом шаге в пункт 10 можно попасть из пункта 8 или 9, причем только одним способом: из пункта 8 – дорогой 8–10, при этом придется преодолеть 3 км, из пункта 9 – дорогой 9–10, преодолев
6 км. Результатом оптимизации четвертого шага являются первые две стрелки (на ребрах (8; 10) и (9; 10) сети).

Переходим к оптимизации третьего шага. Для этого проанализируем все возможные варианты движения из пунктов 5, 6, 7. Для каждого пункта выбираем условное оптимальное решение (оптимальный маршрут в пункт 10) и вычисляем соответствующее минимальное расстояние. Из пункта 5 можно следовать либо через пункт 8, либо через пункт 9. В первом случае расстояние равно 5 + 3 = 8 км, во втором – 7 + 6 = 13 км. Значит, условный оптимальный маршрут из пункта 5 в пункт 10 проходит через пункт 8. На ребре (5; 8) ставим стрелку, а в кружке 5 записываем минимальное расстояние 8 = 5 + 3, ребро (5; 9) остается без стрелки. Аналогично для пункта 6 находим условно-оптимальный маршрут 6–8–10 с расстоянием до пункта 10 в 5 км, для пункта 7 – условно-оптимальный маршрут 7–9–10 с расстоянием в 10 км.

Далее оптимизируем путь для второго шага процесса. Здесь находим оптимальный маршрут в пункт 10 из каждого пункта второй группы (2, 3, 4).

Для каждого из этих пунктов надо проанализировать все возможные маршруты из него и найти сумму расстояний до ближайшего пункта третьей группы и условно-минимальное расстояние на оптимальном продолжении пути в пункт 10 от этого пункта, которое найдено в результате оптимизации третьего шага. Из всех возможных маршрутов выбираем тот, для которого эта сумма меньше (если суммы равны, выбираем любой маршрут). Для пункта 2 оптимальным будет маршрут протяженностью в 15 км, проходящий через пункт 7, поскольку по этому маршруту получаем минимальную из сумм (9 + 8) и (5 + 10); для пункта 3 – маршрут, проходящий через пункт 6 с расстоянием 4 + 5 = 9 км; для пункта 4 – маршрут через пункт 6 с расстоянием 1 + 5 = 6 км.

Оптимизируем первый шаг. Сравним три возможных маршрута: через пункты 2, 3, 4. Устанавливаем, что наикратчайшим будет маршрут, пролегающий через пункт 4, как маршрут, отвечающий минимальной из сумм (3 + 15), (8 + 9), (4 + 6), равной 10.

Этап условной оптимизации закончен, и остается проследить оптимальный маршрут. Движение из пункта 1 по сети в направлении стрелок позволяет сформировать следующий самый короткий маршрут: 1–4–6–8–10. Его протяженность составляет 10 км. На рисунке он выделен жирной линией.

Примененный для решения задачи метод динамического программирования дает возможность одновременно с оптимальным маршрутом из пункта 1 в пункт 10 найти всю систему оптимальных маршрутов относительно пункта 10 для данной сети дорог. Все эти маршруты приведены в табл. 21.

Таблица 21

Исходный пункт	Оптимальный путь в пункт 10, проходящий через пункты	Кратчайшее расстояние
	7 и 9
	6 и 8
	6 и 8
	–
	–

Вопросы для самоконтроля

1. Примеры задач динамического программирования, их особенности и геометрическая интерпретация.

2. Многошаговые процессы в динамических задачах.

3. Принцип оптимальности и рекуррентные соотношения.

4. Задача выбора кратчайшего пути и алгоритм ее решения.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Задание 1.Решить графически и методом искусственного базиса задачи линейного программирования.

1.1. ;	1.6. ;
1.2. ;	1.7. ;
1.3. ;	1.8. ;
1.4. ;	1.9. ;
1.5. ;	1.10. ;

Задание 2. Решить задачу симплексным методом. Построить двойственную задачу и записать ее решение.

2.1. ;	2.6. ;
2.2. ;	2.7. ;
2.3. ;	2.8. ;
2.4. ;	2.9. ;
2.5. ;	2.10. ;

Задание 3.Найти решение транспортной задачи.

3.1.	3.6.
3.2.	3.7.
3.3.	3.8.
3.4.	3.9.
3.5.	3.10.

Задание 4.Найти методом Гомори максимум или минимум целевой функции при заданной системе ограничений. Во всех задачах и – целые .

4.1. ;	4.6. ;
4.2. ;	4.7. ;
4.3. ;	4.8. ;
4.4. ;	4.9. ;
4.5. ;	4.10. ;

Задание 5.С помощью метода Лагранжа найти точки условных экстремумов данных функций.

5.1.	при .
5.2.	при .
5.3.	при .
5.4.	при .
5.5.	при .
5.6.	при .
5.7.	при .
5.8.	при .
5.9.	при .
5.10.	при .

Задание 6. На рисунке показана сеть дорог. в таблице приведены расстояния (в километрах) между промежуточными пунктами сети.

Исходя из данных рисунка и таблицы выполнить следующее:

· методом динамического программирования найти самый короткий маршрут из пункта 1 в пункт 10;

· составить таблицу оптимальных маршрутов из всех остальных пунктов сети в пункт 10 и указать кратчайшее расстояние от каждого пункта до пункта 10.

	Номер задания
6.1	6.2	6.3	6.4	6.5	6.6	6.7	6.8	6.9	6.10
С12
С13
С14
С25
С27
С35
С36
С37
С45
С46
С47
С58
С59
С68
С69
С79
С8,10
С9,10

ТЕСТЫ ДЛЯ ПРОВЕРКИ УСВОЕНИЯ
ТЕМ ПРОГРАММЫ КУРСА

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

Тест 1 предусматривает выбор ответов из предложенных (задания закрытого типа 1.1–1.25), тест 2 – написание кратких ответов (задания открытого типа 2.1–2.4).

К каждому заданию теста 1 даны 5 вариантов ответов, из которых только 1 верный. В бланке ответов с номерами заданий следует поставить “+” в клетке, номер которой соответствует номеру выбранного ответа. Затем необходимо решить задания теста 2, ответы записав на бланке рядом с номерами заданий. После этого рекомендуется сравнить полученные результаты с приведенными в данном издании ответами.

Тест 1

1.1.На каком из чертежей отмеченная полуплоскость является решением неравенства ?

х1 х2 х1 х2 1)

2)

3)	5)
4)

1.2. Чему равны координаты вектора , если функция ?

Варианты ответа:

1) ; 4) ;

2) ; 5) .

3) ;

1.3. На каком из чертежей линия соответствует целевой функции ?

1)	2)
3)	5)
4)

1.4. В задаче линейного программирования

;

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

Указать координаты точки, в которой функция достигает наибольшего значения.

Варианты ответа:

1) ;

2) ;

3) ;

4) ;

5) .

–2х1 + х2 = 2

х1 = 4

9х1 + 4х2 = 18

х1

1.5. В каком из вариантов задача линейного программирования не имеет минимума?

1)

2)

3)	5)
4)

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

;

Варианты ответа:

1) ;	2) ;	3) ;
4) ;	5) .

1.7. Условия ЗЛП

;

занесли в следующую симплексную таблицу:

БП	сБ	А0	x1	x2	x3	x4	x5
x3			(2)
x4
x5
		–6	–3

Чему равен найденный разрешающий элемент?

Варианты ответа:

1) 2;

2) 7;

3) 9;

4) 4;

5) 1.

1.8. Вычислить по правилу прямоугольника элемент, стоящий на месте цифры 9 следующей таблицы:

БП

сБ

А0

x1

x2

x3

x4

x5 Наши рекомендации Метод Гомори. Целочисленное решение Целочисленное программирование Целочисленное программирование Целочисленное программирование Метод Гомори. Целочисленное решение Целочисленное программирование Целочисленное программирование Целочисленное программирование. Метод Гомори. Целочисленное решение Целочисленное программирование ← Предыдущая страница | Следующая страница →