книги / Некоторые главы математического программирования

Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Пермский национальный исследовательский политехнический университет»

Кафедра прикладной математики

Н.Г. Третьякова

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

Утверждено Редакционно-издательским советом университета

в качестве учебно-методического пособия

Издательство Пермского национального исследовательского

политехнического университета

2020

1

УДК 519.85(075.8) Т66

Рецензент:

канд. физ.-мат. наук, доцент М.А. Севодин (Пермский национальный исследовательский политехнический университет)

Третьякова, Н.Г.

Т66 Некоторые главы математического программирования : учеб.-метод. пособие / Н.Г. Третьякова. – Пермь : Изд-во Перм. нац. исслед. политехн. ун-та, 2020. – 58 с.

ISBN 978-5-398-02385-5

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

Предназначено для студентов экономических специальностей дневной и заочной форм обучения.

УДК 519.85(075.8)

2

3

ВВЕДЕНИЕ

Предлагаемое учебно-методическое пособие является продолжением учебного пособия Н.Г. Третьяковой «Введение в математическое программирование» и включает в себя два важных раздела математического программирования: дискретное программирование и динамическое программирование.

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

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

В конце пособия приведены задания для контрольных или самостоятельных работ (25 вариантов). Задачи носят учебный характер и рассчитаны на вычисления вручную (без использования компьютера).

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

Теоретический материал, необходимый для решения задач 1–2, приведен в пособии Н.Г. Третьяковой «Введение в математическое программирование», поэтому в данном пособии показан только пример решения задачи 2.

4

Глава 1. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

1.1.Задачи целочисленного программирования

иметоды их решения

Дискретное программирование – это область математики,

в которой изучаются экстремальные задачи, на все или некоторые переменные которых наложено условие целочисленности, а множество решений конечно. Многие экономические задачи имеют дискретную природу. Это задачи с физической неделимостью. К примеру, нельзя построить 3,5 завода или выпустить на рынок 7,8 самолета. Кроме этого, дискретными являются экстремальные задачи с логическими переменными. Такие переменные могут принимать лишь два значения – нуль или единица (они называются булевыми переменными).

Иногда вместо термина «дискретное программирование» употребляется термин «целочисленное программирование», но они неравнозначны. Целочисленное программирование является частным случаем дискретного программирования.

Задач дискретного программирования множество. К наиболее известным задачам дискретного программирования относятся:

–задачи с неделимостями («задача о рюкзаке»);

–задачи с булевыми переменными («задача о назначении»);

–задачи комбинаторного типа («задача коммивояжера (бродячего торговца)») и другие.

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

Математическая модель такого рода задач записывается следующим образом:

z n cj xj max min

j 1

5

при таких ограничениях:

xj – целые числа j 1, p , p ≤ n.

Если p = n, то имеем полностью целочисленную задачу, если же p < n , то задачу называют частично целочисленной.

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

Методы решения задач целочисленного программирования можно разделить на две группы: точные и приближенные.

Универсальными методами решения задач целочисленной оптимизации (программирования) являются метод отсечения (метод Гомори) и метод «ветвей и границ» (комбинаторный метод). Это точные методы решения. Недостатком этих методов является их слабая сходимость.

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

Рассмотрим точные методы решения.

1.2. Метод отсечения (метод Гомори)

Идея решения задачи целочисленного программирования методом Гомори состоит в следующем. Данная задача решается методами линейной оптимизации без учета условий целочисленности. Если по-

6

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

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

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

Рассмотрим алгоритм решения целочисленной задачи линейного программирования, предложенный Р. Гомори.

Математическая модель задачи имеет следующий вид:

– целевая функция:

Алгоритм Гомори:

1.Решаетсязадача(1.2.1)–(1.2.3) безучетаусловийцелочисленности.

2.Проверяется полученное оптимальное решение на целочисленность. Если полученное оптимальное решение целочисленно, то

7

оно, т.е. решение задачи (1.2.1)–(1.2.3), является и оптимальным решением задачи (1.2.1)–(1.2.4) и решение завершено. Если хотя бы одна из переменных в оптимальном плане нецелочисленна, то переходят к следующему пункту. Если задача (1.2.1)–(1.2.3) не имеет решений, то и исходная задача (1.2.1)–(1.2.4) тоже неразрешима.

3.Строится дополнительное ограничение (правильное отсечение), которое отсекает от области допустимых решений ту ее часть, которая содержит полученное нецелочисленное оптимальное решение задачи (1.2.1)–(1.2.3) и не содержит ни одного целочисленного решения исходной задачи (1.2.1)–(1.2.4).

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

За конечное число шагов целочисленное оптимальное решение задачи будет найдено, если оно существует.

Правильное отсечение Гомори. Систему ограничений задачи (1.2.1)–(1.2.3) после каждой итерации можно представить в виде

где {СП} – множество свободных переменных; {БП} – множество базисных переменных.

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

Пусть некоторые βi нецелые. Предположим, например, что компонента i0 нецелая. Рассмотрим соответствующее равенство из системы

(1.2.5), для которого выполненоусловие оптимальности, т.е.

8

Как известно, наибольшая целая часть числа a, его не превосходящая, обозначается [a], а дробная положительная часть – {а}. Причем а = [а] + {а}, 0 ≤ {а} < 1. Тогда правильное отсечение Гомори определяется неравенством

Пример 1

Решить задачу целочисленного программирования, т.е. найти максимум функции z:

z = 4x1 + 3x2 (max)

при следующих условиях:

4x1 3x2 16,16x1 7x2 48;

x1 ≥0, x2 ≥0, x1 и x2 – целые числа.

Решение

Решаем данную задачу без условия целочисленности симплексметодом. Записываем условия задачи в специальном виде:

4x1 3x2 y1 16,16x1 7x2 y2 48;

–z + 4x1 + 3x2 = 0 (min).

СоставляемС-таблицу (табл. 1) и находимоптимальноерешение. Оптимальное решение (xнц – нецелочисленное решение):

xнц* = (8/5, 16/5, 0, 0); zmax = 16.

Две компоненты xнц*– дробные. Построим правильное отсечение по строке x1 последней из табл. 1:

9

53 1320 у1 203 у2 0,

так как

Преобразуем:

1320 у1 203 у2 53 ;

1320 у1 203 у2 у3 53.

Вводим базисную переменную у4:

1320 у1 203 у2 у3 y4 53.

10