Конспект лекций по курсу «Математическое программирование»

f_min = 2•4 + 18•3 + 15•1 + 15•5 = 152

Потребность пункта В₂ удовлетворена не полностью.

                 Таблица 5.18

Пн По	В1	В2	В3	Запасы
А1	2	4 2	3 18	20
А2	1 15	5 15	4	30
Потре бности	15	25	18

 

6. ЦЕЛОЧИСЛЕННОЕ  ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

 

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

6.1. Общая постановка  задачи целочисленного линейного  программирования (ЗЦЛП).

Мы будем  рассматривать только полностью  целочисленные задачи, в которых требование целочисленности наложено на все переменные. Общий вид такой ЗЦЛП отличается от  ЗЛП только тем, что ко всем  переменным предъявляется требование целочисленности. В частности, в каноническом виде ЗЦЛП ставится так:

 

 

                                         (6.1)

                                   

Для ЗЦЛП используется та же терминология, что и для  ЗЛП: целевая функция, допустимое решение, оптимальное решение и т.д. Если в ЗЦЛП отбросить требование целочисленности, то получится так называемая ослабленная задача. Ослабленная задача является ЗЛП, в то время как ЗЦЛП таковой не является. Дело в том, что требование целочисленности переменных нельзя записать в виде линейного ограничения. Аналитически его записать можно. Действительно, обозначим через [a] целую часть числа а, т.е. наибольшее целое, которое не больше а. Например,  [3.4] =3; [-7.2]= -8. Требование целочисленности переменной x_j можно записать  так: x_j -[x_j ] =0. Однако это соотношение не является линейным. Таким образом, нельзя сказать, что ЗЦЛП – частный случай ЗЛП – она вообще не является ЗЛП.

Для ЗЦЛП не существует такого универсального  эффективного метода решения, каким является симплекс-метод  для ЗЛП. Из точных методов решения  отметим метод отсечения Гомори и комбинированный метод ветвей и границ. Суть этого комбинированного метода мы изложим.

На практике большинство  ЗЦЛП решается приближенно. При этом часто приходится разрабатывать  приближенный метод, учитывающий специфические  особенности задачи.

Приведем примеры ЗЦЛП.

 

6.2. Целочисленная  задача об использовании сырья.

Предприятие выпускает  n видов штучной продукции стоимостью за штуку. Для  изготовления продукции используется  m видов сырья, запасы которого на предприятии равны соответственно . Известна (m X n) – матрица (a_ij), в которой - расход i – го сырья на производство единицы продукции j –го вида. Требуется составить такой план производства, при котором выручка от реализации продукции была бы наибольшей.

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

f =

→  max

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

                                        

 

Здесь - количество  продукции j –го вида.

Это задача целочисленного линейного программирования.

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

 

6.3. Задача о рюкзаке.

Целочисленная задача об использовании сырья не является ярко выраженной ЗЦЛП. К типичным ЗЦЛП относятся т.н. комбинаторные оптимизационные задачи. В комбинаторных задачах имеется конечное множество вариантов, из которых нужно выбрать оптимальный. Примером такой задачи является задача о рюкзаке.

Имеется рюкзак вместимостью V и n предметов объемами v₁, v₂ , ...,v_n и стоимостями с₁,  c₂ ,..., c _n . Требуется упаковать рюкзак так, чтобы стоимость упакованных предметов была максимальной.

Составим математическую модель этой задачи.

Пусть x_j – переменная, принимающая только два значения: 0 или 1, причем x_j =0, если j-й предмет не упаковывается в рюкзак; x_j = 1, если j-й предмет упаковывается в рюкзак. Тогда задача записывается так:

                                    

 при ограничениях

                                                                          

 

Это ЗЦЛП, называемая задачей  булева программирования. Ограничения  задачи можно записать иначе:

        

           

6.4. Решение  ЗЦЛП методом округления.

 

Метод округления – простейший метод  приближенного решения ЗЦЛП. Его  сущность состоит в том, что решается ослабленная задача (как задача линейного  программирования) и полученное оптимальное  решение ЗЛП округляется до целочисленного решения. Этот метод имеет два существенных недостатка:

1. в результате округления может получиться недопустимое решение;
2. решение, полученное в результате округления, являясь допустимым, может значительно отличаться от оптимального.

Пример 1.

Решив геометрически  ослабленную задачу, получаем  оптимальное  решение:

 

Произведем  округления:

1. x₁=2; x₂=0. Получим недопустимое решение - не удовлетворяется   ограничение 7x₁+4x₂<=13 (действительно,  7*2+4*0<=13 – ложное неравенство).

                2)х₁=1; х₂=0. Это допустимое решение. Значение целевой функции f=21*1+11*0=21, что сильно отличается  от оптимального значения.

Оптимальное решение  этой ЗЦЛП  таково: х₁=0;  х₂=3; f_max =33.

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

 

6.5. Метод ветвей и границ.

 

Этот метод  точного решения ЗЦЛП чаще всего  используется на практике. Он состоит  в следующем.

Сначала решается ослабленная задача. Если полученное оптимальное решение целочисленное, то ЗЦЛП решена. Если же оптимальное решение ЗЛП не является целочисленным, то производим "ветвление" следующим образом. Пусть переменная х_s приняла в оптимальном решении значение q_s,  которое не является целым. Тогда рассматриваем две ЗЦЛП. Первая  получается добавлением ограничения х_s <=[q_s],  вторая – добавлением ограничения х_s >=[q_s] + 1, где [q_s] - целая часть числа q_s .

Каждая из этих двух задач аналогичным образом  может разбиться еще  на две задачи т.д.

Если в результате решения какой-либо из задач получается целочисленный оптимальный план, то значение А целевой функции при этом плане играет роль "границы": если в результате решения очередной ЗЛП выяснится, что оптимальное значение целевой функции "хуже" А, то такая задача  "не ветвится".

Недостаток  метода ветвей и границ состоит в  том, что часто оптимальное решение  ЗЦЛП достигается после очень  большого числа ветвлений.

Вернемся к  ЗЦЛП примера 1.

    

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

 

                     Исходная ЗЦЛП №1

( оптимальный план  )

 

 

 

 

 

 

 

 оптимальный  план                                                           ОДР пуста. 

                                             

 

 

 

 

                                                         

   

оптимальный план                                                             оптимальный  план

  х₁=1, х₂=1, f_max=32                                                             х₁= , х₂=2, f_max=37

A=32

 

 

 

 

 

 

оптимальный план                                                            ОДР пуста

х₁=0, х₂= , f_max=35,75

 

 

              

        

 

 

 

Оптимальный план                                                                        ОДР пуста

х₁=0, х₂=3, f_max=33>A

 

Оптимальный план ЗЦЛП: х₁=0, х₂=3, f_max=33.

 

 

7. ОБЩАЯ  ПОСТАНОВКА И РАЗНОВИДНОСТИ ЗАДАЧ  МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

 

Математическое  программирование - обширная область  знаний. Мы рассмотрели далеко не полностью  один из разделов - линейное  программирование.

Общая математическая схема задачи математического программирования такова: дана некоторая функция

z = f(x₁, x₂, . . . , x_n)     (7.1)

и некоторая  система ограничений , наложенных на переменные x₁, x₂, . . . , x_n:

Требуется  найти  такой  набор  значений  переменных x₁, x₂, . . . , x_n, который удовлетворяет ограничениям (7.2), и при этом условии минимизирует или максимизирует функцию (7.1).

Если все  фигурирующие в (7.1) и (7.2) функции линейны, то мы имеем ЗЛП. В противном  случае получается задача  нелинейного  программирования.

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

В некоторых  задачах математического программирования ОДР состоит из дискретного множества точек. Такие задачи называются дискретными оптимизационными задачами. Например, если в ЗЛП потребовать, чтобы переменные принимали только целые значения, то получится дискретная оптимизационная задача - задача целочисленного линейного программирования. Дискретные задачи, как правило, сложнее непрерывных. По задачам дискретной оптимизации в настоящее время проводятся интенсивные научные исследования.

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

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

По математическому  программированию написано уже много  книг. Приводимая  литература - незначительная часть их. Но в ней можно найти  изложение основных положений математического  программирования, а также ссылки на другие источники.

ЛИТЕРАТУРА

1. Крушевский  А.В., Швецов К.М. Математическое  программирование и моделирование  в экономике.-К.: Вища шк., 1979

2. Кузнецов Ю.Н., Кузубов В.М., Волощенко А.Б. Математическое  программирование.-М.: Высш.шк.,1980

3. Таха  X.   Введение  в исследование  операций. (В 2-х книгах).- 
М.:Мир,1985

4. Мину М. Математическое программирование. Теория и 
алгоритмы.-М.: Наука, 1990.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Содержание

1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ГАУССА – ЖОРДАНА........................................................

  1.1. Основные  понятия .......................

2. Приведение системы линейных уравнений к жордановой форме........
3. Понятие общего, частного и базисного решений.....

2.ОБЩИЕ СВОЙСТВА  ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ       ................

2.І. Пример  задачи линейного программирования -

задача об использовании  оборудования.....

2.2. Задача об  использовании сырья..........

2.3. Задача составления  рациона (задача о диете).

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

2.5. Геометрический  метод решения ЗЛП.

2.6. Канонический  вид ЗЛП.

2.7. Понятие опорного  плана ЗЛП.

3. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика  и основные этапы симплекс  –метода

3.2.Табличный вид ЗЛП.  Симплекс - таблицы.

3.3. Условие оптимальности опорного плана.

3.4. Условие  неразрешимости ЗЛП из-за неограниченности  снизу на ОДР целевой функции.