Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Matematika / Модуль 1 / Лекция 4(Дискретное прогр.).doc
Скачиваний:
82
Добавлен:
26.04.2015
Размер:
125.95 Кб
Скачать

Лекция 4

Дискретное программирование

Вопросы:1. Дискретное программирование, задачи и сущность методов

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

3. Метод сечений

4. Задача коммивояжера

1. Дискретное программирование, задачи и сущность методов

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

В экономике существует огромное количество задач с дискретной природой. В первую очередь это задачи с физической неделимостью многих факторов и объектов расчета (1,5 кровати и 0,3 завода). Дискретными являются задачи с логическими переменными, принимающими только два значения: 0 и 1 (да и нет). Наиболее распространенными задачами дискретного программирования являются задачи:

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

2) о назначениях (выбора), в которой определяется наиболее рациональное использование потенциала сотрудников при выполнении определенных работ;

3) коммивояжера,в которой определяется минимальный путь агента, проходящий через необходимые пункты возможного сбыта продукции;

4) транспортная,один из случаев задачи дискретного программирования.

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

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

Универсальных, эффективных методов решения ЗДП не создано. И, как показали исследования, их создание, по-видимому, невозможно. Существуют два направления развития методов дискретного программирования:

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

  2. развитие приближенных методов решения. Обычно применяемых при решении задач большой размерности.

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

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

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

Рассмотрим задачу (типа задачи о рюкзаке) с двумя неизвестными и с единственным ограничением. 10х1+12х2 59, х1, х2,

F(x) = 10х1+ 11х2

Если использовать для решения графический метод,

получим: х1= 0 х1= 5,9

х2= 4,9 х2= 0

Если не учитывать требование целочисленности,

то Fmax= 59, х1= 5,9; х2= 0.

Если округлить значения переменных до целых (х1= 6; х2= 0), то ограничения задачи будут нарушены. Значения, которые могут принимать переменные находятся в узлах сетки. На этом простом примере видно, что это х1= 1; х2= 4,Fmax= 54.

Пример показал, что: 1) округлять значения переменных нельзя;

2) точка оптимума может не иметь ничего общего с

непрерывным оптимумом.

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