Тема Целочисленное программирование - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Целочисленное и бинарное программирование 1 108.08kb.
Тематика курсовых работ по математическим методам кибернетики 1 16.4kb.
Целочисленное программирование. Метод ветвей и границ 1 92.03kb.
Тема технология программирование 1 70.3kb.
Целочисленное программирование 6 475.77kb.
7. целочисленное программирование 10 870.02kb.
Целочисленное программирование 1 46.81kb.
Тема: «Математическое программирование» 8 504.92kb.
Методические указания к лабораторным работам и домашним заданиям... 6 327.14kb.
Программа вступительного экзамена по специальности 05. 13. 18 Математическое... 1 112.81kb.
Варианты заданий к контрольной работе 1 22.41kb.
Решение задачи. Рассмотрим пример. Пусть имеется ряд предметов П1... 1 35.44kb.
Направления изучения представлений о справедливости 1 202.17kb.

Тема Целочисленное программирование - страница №1/3

Тема 5. Целочисленное программирование

Постановка задачи


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

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

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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) , при котором линейная функция принимает максимальное или минимальное значение при ограничениях



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

В настоящее время наиболее широкое применение находят два основных метода решения задач целочисленного программирования:

а) метод отсечений;

б) комбинаторный метод.

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

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


Графическое решение задачи целочисленного линейного программирования


Рассмотрим случай, когда число неизвестных равно двум. Для решения задачи графическим методом прежде строят многоугольник решений без условия целочисленности. Условию целочисленности переменных удовлетворяют не все координаты точек области допустимых решений, поэтому область допустимых решений ослабленной задачи (без условия целочисленности) заменяется на выпуклый многоугольник, содержащий только допустимые точки с целочисленными координатами. Чтобы найти максимум или минимум целевой функции на выпуклой оболочке строят вектор градиент С(с1, с2). Передвигая прямую Z =c1x1+c2x2 в направлении вектора С, в результате чего находят точку, в которой целевая функция принимает оптимальное значение. Затем определяем координаты точки экстремума функции и вычисляем значение целевой функции в этой точке.

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


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

Условию целочисленности удовлетворяют лишь 12 точек, отмеченных на рисунке. Чтобы найти точку, координаты которой определим решение исходной задачи, заменяя многоугольник ОАВС многоугольником OKEMNF, содержащий все допустимые точки с целочисленными координатами.

Для определения максимального значения целевой функции на многоугольнике OKEMNF построим вектор градиент С(2; 4) и прямую . Построенную прямую передвигаем в направлении вектора градиента до тех пор, пока она не пройдет через последнюю общую точку ее с этим многоугольником. Координаты полученной точки Е(1; 3) и являются оптимальным решением задачи, а значение целевой функции в ней Fmax=14 является максимальным.

Метод Гомори


Метод Гомори решения задач целочисленного программирования является методом отсечения.

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

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

Для нахождения целочисленного решения задачи методом Гомори используется следующий алгоритм.



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

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

- оно должно быть линейным;

- должно отсекать найденный оптимальный нецелочисленный план;

- не должно отсекать ни одного целочисленного плана.

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

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

Для изложения метода вводим следующие понятия. Пусть a – действительное число.

Под целой частью некоторого числа а понимается максимальное целое число [a], не превосходящее данного.

Под дробной частью некоторого числа а понимается наименьшее неотрицательное число такое, что разность между ним и а есть [a] – целая часть числа).

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

Обозначим и целые части чисел и . Величины дробных частей и () определяются следующим образом





  1. Составляем неравенство Гомори и включаем его в систему ограничений исходной задачи.

Для этого по производящей строке симплексной таблицы выписывается уравнение, предполагая, что первые m переменных являются базисными для данного оптимального плана

или

Переносим все целые части коэффициентов в одну сторону, оставляя все дробные в другой:





Так как <1, то заменяя в правой части , получим строгое неравенство



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





  1. Неравенство преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу.

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

Пример. Методом Гомори найти решение задачи целочисленного программирования, состоящей в определении максимального значения функции при условии



Решение. Выравнивая неравенства с помощью вспомогательных переменных х3, х4, получаем задачу линейного программирования в канонической форме:

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



Б

СБ

В

С1=5

С2=11

С3=0

С4=0

а1

а2

а3

а4

а3

0



3

4

1

0

а4

0

10

2

5

0

1

j =Zj–Сj

0

-5

-11

0

0







СБ

В

С1=5

С2=11

С3=0

С4=0

а1

а2

а3

а4

а2

11





1



0

а4

0





0



1

j =Zj–Сj





0



0

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





Теперь составляем для найденных значений дробных частей неравенство Гомори:



.

Выравниваем неравенство Гомори с помощью новой вспомогательной переменной х5, переносим свободный член уравнения в правую часть и получаем новое ограничение:



.

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




Б

СБ

В

С1=5

С2=11

С3=0

С4=0

С5=0

а1

а2

а3

а4

а5

а2

110





1



0

0

а4

0





0



1

0

а5

0





0



0

1

j =ZjСj





0



0

0




Б

СБ

В

С1=5

С2=11

С3=0

С4=0

С5=0

а1

а2

а3

а4

а5

а2

11

1

0

1

0

0

1

а4

0



0

0



1



а1

0



1

0



0



j =ZjСj



0

0



0


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







и новое неравенство Гомори имеет вид:

Выравниваем неравенство Гомори с помощью новой вспомогательной переменной х6, переносим свободный член уравнения в правую часть и получаем новое ограничение: .

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




Б

СБ

В

С1=5

С2=11

С3=0

С4=0

С5=0

С6=0

а1

а2

а3

а4

а5

а6

а2

110

1

0

1

0

0

1

0

а4

0



0

0



1



0

а1

0



1

0



0



0

а6

0



0

0



0



1

j =ZjСj



0

0



0



0




Б

СБ

В

С1=5

С2=11

С3=0

С4=0

С5=0

С6=0

а1

а2

а3

а4

а5

а6

а2

110

1

0

1

0

0

1

0

а4

0

5

0

0

0

1

-1

-2

а1

0

0

1

0

0

0

-2

1

а3

0



0

0

1

0

2

-3

j =ZjСj

11

0

0

0

0

1

5

Таким образом, найдено оптимальное решение задачи целочисленного программирования: Zmax =11 при .



Замечания:

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



следующая страница >>



Хорошие похороны — не импровизация: им нужно посвятить жизнь. Огюст Детёф
ещё >>