- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
32. Целочисленное программирование
Целочисленное программирование (ЦП) – это наиболее важный раздел дискретного программирования. Задачи дискретного программирования отличаются тем, что на переменные накладывается требование дискретности, в частном случае – целочисленности. В качестве примеров можно привести задачи о раскрое (разд. 4.11.5), о ранце, коммивояжера и др.
Характерные источники целочисленности (дискретности):
неделимость объектов, представляемых переменными (например, x – число рабочих или отправляемых вагонов);
вариантность типа “да-нет” (например, включать или нет данный пакет в портфель ценных бумаг);
заданность возможных значений нормативными документами (например, сечения проводов, диаметров труб, размеров профилей и т.п.);
комбинаторность (например, размещение объектов, порядок обхода объектов, упорядочение);
логические условия (например, фиксированные затраты имеют место только при производстве продукции).
Различают задачи полностью целочисленные/дискретные и частично целочисленные (смешанные). В последних требование целочисленности накладывается не на все переменные.Любой ряд дискретных значений может быть представлен линейной комбинацией целочисленных переменных. Поэтому дискретная задача легко сводится к целочисленной за счет значительного увеличения числа переменных.
В этой главе рассматриваются только линейные целочисленные задачи.
7.1. Проблема целочисленности
На первый взгляд может показаться, что целочисленная задача решается проще непрерывной. При малой размерности и узких диапазонах переменных задачу можно решить простым перебором. В других случаях необходимы соответствующие методы.
Несмотря на линейность модели допустимое множество целочисленной задачи не является выпуклым. Так, в полностью целочисленной задаче оно представляет собой множество отдельных точек, имеющих целочисленные координаты. Методы линейного программирования базируются на выпуклости допустимого множества и поэтому непосредственно не могут быть применимы к целочисленным задачам.
Можно, конечно, пренебречь требованием целочисленности и использовать один из методов ЛП, но тогда, за редким исключением, результат не будет целочисленным. Округление дробных значений переменных проблематично. Действительно, так как оптимальное решение непрерывной задачи лежит в вершине допустимого множества, округление может привести к недопустимости. При двух дробных переменных имеется 4, а при n переменных – 2n вариантов округления! Какие из них дают допустимые решения, можно определить только после проверки всех ограничений. При этом следует иметь в виду, что, во-первых, целочисленная задача может оказаться неразрешимой несмотря на разрешимость непрерывной задачи; во-вторых, допустимость округленного решения еще не означает его оптимальность. Проиллюстрируем последний тезис известной задачей о садовнике.
По расчетам садовника требуется внести в почву комплексные удобрения в количестве 107 кг. Удобрения продаются только в расфасованном виде: 1) мешок весом 35 кг стоит 140 руб.; 2) мешок весом 24 кг стоит 120 руб. Необходимо определить вариант закупки удобрений с минимальными затратами.
Запишем модель задачи:
L=140x1+120x2min; 35x1+24x2 107; x1, x2 0, int (целые).
Если пренебречь целочисленностью, то легко увидеть, что оптимальным будет решение x1= 3 , x2=0.
Если округлить его по правилам арифметики, то получим недопустимое решение. Округление в большую сторону (x1=4, x2=0) приводит к допустимости, но является ли такое решение оптимальным?
Чтобы ответить на этот вопрос, рассмотрим все возможные Таблица 7.1
x1 |
x2 |
L |
3 |
0 |
- |
4 |
0 |
560 |
3 |
1 |
540 |
2 |
2 |
520 |
1 |
3 |
500 |
0 |
4 |
- |
0 |
5 |
600 |
целочисленные решения (табл.7.1). Прочерк в графе критерия означает недопустимость.
Как видно из таблицы, оптимальным является решение x1*=1, x2*=3, которое принципиально отличается от непрерывного: закупать надо в основном мешки 2-го типа, тогда как по нерерывному решению – только 1-го типа. Кроме того, округленное допустимое решение оказалось далеким от оптимального: затраты в нем выше минимальных на 12%. ▲
Другую особенность свойств целочисленных задач покажем также на конкретном примере:
L=21x1+11x2max; 7x1+4x2 13; x1, x2 0, int.
Как и в задаче о садовнике, рассмотрим все возможные целочисленные решения. При этом сначала возьмем решение x1=1, x2=1 и решения, окружающие его (табл. 7.2). Целочисленные точки и ограничение показаны на рис. 7.1.
x1 |
x2 |
L |
1 |
1 |
32 |
0 |
0 |
0 |
0 |
1 |
11 |
1 |
0 |
21 |
0 |
2 |
22 |
1 |
2 |
- |
2 |
2 |
- |
2 |
1 |
- |
2 |
0 |
- |
0 |
3 |
33 |
Из таблицы следует, что в точке (1, 1) имеет место локальный экстремум, а глобальный максимум достигается в точке (0, 3). В непрерывной линейной задаче любой локальный экстремум является глобальным. То что целочисленная задача может иметь локальные экстремумы, необходимо учитывать при использовании методов частичного перебора. ▲ В ряде случаев решение целочисленной задачи находят, решая ее как непрерывную. Так, если в оптимальном решении непрерывной задачи нецелочисленные значения переменных велики (их порядок >102), округление до целых оправдано: возможные нарушения условий и отклонение от оптимальности пренебрежимо малы. При особых свойствах целочисленной задачи решение ее как непрерывной всегда дает целочисленный результат. Такой исход имеет место, если все вершины допустимого множества целочисленные. Многогранное множество, обладающее этим свойством, называется целочисленным. Определим условия, при которых множество оказывается целочисленным.
Возьмем многогранное множество M(B):
; (7.1)
(7.2)
где все aij – фиксированные целые числа, B =(b1,b2,…, bm)Т и m<n (ранг матрицы [aij] равен m.) Для него справедлива следующая теорема.
Теорема. Для того чтобы все вершины многогранного множества M(B) при любом целочисленном векторе B были целочисленными, необходимо и достаточно, чтобы каждый минор порядка m матрицы условий [aij] был равен либо 0, либо +1 или –1. Если вместо равенств (7.1) множество задается неравенствами, указанные в теореме значения относятся ко всем минорам матрицы [aij].
Класс задач, удовлетворяющих теореме, очень узок (это транспортные задачи, задачи о назначениях и др.). Такие задачи относят к лекгоразрешимым (по Дж. Эдмондсу), так как для них существуют полиномиальные алгоритмы (время или число итераций растет полиномиально с увеличением размерности задачи). Остальные целочисленные задачи входят в класс трудноразрешимых задач (класс NP по Карпу и Куку).
Для решения таких задач применяются различные подходы. Из точных методов можно назвать следующие:
методы отсечений;
метод ветвей и границ;
метод построения последовательности планов
модификации динамического программирования;
методы последовательного анализа вариантов.
Последние 4 метода входят в группу комбинаторных методов. Кроме точных методов имеется также большое число приближенных методов. Мы остановимся подробнее на первых двух методах как наиболее широко применяемых в пакетах программ, предназначенных для решения задач математического программирования. В ряде из них используются комбинация точных методов, добавление эвристических оценок и другие приемы, позволяющие повысить эффективность алгоритмов.