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

Целочисленным (иногда его называют также дискретным)

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

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

которых на искомые переменные накладывается условие

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

Изучение этого раздела в курсе «Экономико-математические

методы и прикладные модели» вызывается тем, что огромное

количество экономических задач носит дискретный, чаще

всего целочисленный характер, что связано, как правило, с

физической неделимостью многих элементов расчета: например,

нельзя построить два с половиной завода, купить

полтора автомобиля и т.д. В ряде случаев такие задачи решаются

обычными методами, например, симплексным методом,

с последующим округлением до целых чисел. Однако такой

подход оправдан, когда отдельная единица составляет очень

малую часть всего объема (например, товарных запасов); в

противном случае он может внести значительные искажения

в действительно оптимальное решение. Поэтому разработаны

специальные методы решения целочисленных задач, среди

которых можно выделить два направления: методы отсечения

(отсекающих плоскостей) и комбинаторные методы.

Метод отсекающих плоскостей состоит в построении

дополнительных ограничений и применении двойственного

симплексного метода. Представление о комбинаторных

методах дает широко используемый на практике метод

ветвей и границ.

Рассмотрим более подробно один из методов отсекающих

плоскостей, известный как метод Гомори. Метод Гомори для

линейных задач целочисленного программирования основан

на понятии конгруэнтности действительных чисел. Любое

действительное число можно представить в виде суммы его

целой и дробной частей: х = [х] + {х}, где квадратные скобки

означают целую часть, а фигурные — дробную. Например,

7,5 = [7,5] + {7,5} = 7 + 0,5. Неотрицательные числа (для простоты

мы будем рассматривать только их) называются конгруэнтными,

если равны их дробные части. Если обозначать конгруэнтность

чисел символом =, то, например, 7,5 = 0,5; 6,3 = 2,3;

в частности, все целые числа конгруэнтны нулю, поэтому условие

целочисленности переменной Xi можно записать: xi = 0.

По методу Гомори первый этап решения целочисленных

задач не отличается от обычного расчета по симплексному

алгоритму. Если среди значений переменных в оптимальном

плане есть дробные, то составляется дополнительное ограничение,

отсекающее дробную часть решения, но оставляющее

в силе все прочие условия, которым должен удовлетворять

оптимальный план. Это дополнительное ограничение присоединяется

к исходным ограничениям задачи, и вновь применяется

процедура симплексного метода. Алгоритм Гомори

позволяет прийти к оптимальному целочисленному решению

за конечное число шагов.

Конгруэ́нтность (лат. congruens, род. п. congruentis — «соразмерный», «соответствующий»)

17. Сущность задач многокритериальной оптимизации.

В практической деятельности часто встречаются задачи,

заключающиеся в поиске лучшего (оптимального) решения

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

оптимальности. Например, принятие решения о строительстве

дороги в объезд города должно учитывать такие факторы,

как выигрыш города в целом по соображениях экологии,

проигрыш отдельных предприятий и фирм, например, из-за

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

и многие другие. Если такого рода задачи решаются

методами математического программирования, то говорят

о задачах многокритериальной оптимизации. Эти задачи

могут носить как линейный, так и нелинейный характер.

Поскольку методы решения таких задач излагаются ниже

на примере линейных многокритериальных оптимизационных

задач, это объясняет рассмотрение этой темы в данной главе

учебного пособия.

Задачи многокритериальной оптимизации возникают в

тех случаях, когда имеется несколько целей,которые не могут

быть отражены одним критерием (например, стоимость и

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

решений, которая минимизирует или максимизирует все

такие критерии. Если в подобного рода задачах речь идет не

о разнородных критериях некоторой системы, а о сопоставлении

однородных критериев разных ее подсистем (например,

отрасли, группы населения и т.п.), то эти задачи называются

задачами векторной оптимизации.

18. Загальна постановка задачі нелінійного програмування.