- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Пример 7.1. Выведем условие отсечения для задачи
L=2x1+x2 max; 15x1+30x2 96; xj 0, int.
Приводим неравенство к каноническому виду
15x1+30x2+ x3=96
и решаем непрерывную задачу симплекс-методом. Получаем оптимальную симплекс-таблицу
Базис |
А0 |
А1 |
А2 |
А3 |
А1 |
|
1 |
2 |
|
|
|
0 |
3 |
|
Графическое решение показано на рис. 7.4.
Записываем уравнение (7.3) по переменной x1:
x 1+2x2+ x3= . Дробную часть кроме свободного члена имеет только коэффициент при x3. Следуя (7.7), получаем условие отсечения
x3 или x3 6. Очевидно, что в оптимальном решении НЗ оно не выполняется (х3*=0). Условие отсечения можно записать и через основные переменные. Так как х3=96-15х1-30х2, то 96-15х1-30х2 6 и окончательно имеем х1+2х2 6. Граница по этому ограничению показана на рис. 7.4 пунктирной линией. Легко убедиться, что все вершины усеченного множества целочисленные. ▲
При многих нецелых переменных возникает вопрос выбора переменной, по которой следует строить отсечение. Строгого обоснования выбора не имеется. На основе экспериментальных данных рекомендуется брать переменную с наибольшей дробной частью. Второй вопрос относится к способу учета очередного условия отсечения: его можно добавить к условиям исходной задачи и решать задачу заново или после добавления продолжить симплекс-преобразования с полученного оптимального решения, которое стало недопустимым. В алгоритме Гомори применяется второй вариант как более экономичный.
Перед добавлением условие отсечения приводится к равенству:
. (7.8)
Так как небазисные переменные равны нулю, то новая дополнительная переменная . Поэтому рекомендуется для последующего решения применять двойственный симплекс-метод.
Таким образом, согласно 1-му алгоритму Гомори необходимо выполнить следующие действия.
Преобразовать условия задачи так, чтобы все коэффициенты стали целыми.
Решить исходную задачу без учета целочисленности (НЗ) одним из методов линейного программирования. Если непрерывная задача неразрешима, то зафиксировать неразрешимость исходной задачи и перейти на 9.
Проверить решение на целочисленность: если решение целочисленное, то зафиксировать получение оптимального решения и перейти на 9.
Если не все переменные целые, то из оптимальной таблицы выбрать переменную с наибольшей дробной частью.
Выписать из симплекс-таблицы строку с выбранной базисной переменной.
Выделить дробные части коэффициентов в полученном уравнении и записать условие отсечения согласно (7.7).
Привести условие отсечения к равенству (7.8), умножить его на –1 и добавить полученную строку к оптимальной симплекс-таблице. При этом размерность базиса увеличивается на единицу. В качестве недостающей базисной переменной принимается дополнительная переменная из новой строки.
Решить расширенную задачу двойственным симплекс-методом. Если задача разрешима, перейти на 3. Иначе зафиксировать неразрешимость целочисленной задачи.
Конец.
Гомори доказал сходимость этого алгоритма.
Примечание. Как следует из алгоритма, на каждой итерации увеличивается размер таблицы (число условий) на единицу. Для ограничения размера используется такой прием. Как только дополнительная переменная какого-либо условия отсечения снова становится базисной (но уже положительной!), строка с ней удаляется из таблицы. Если велся столбец этой переменной, то он тоже удаляется. Подобное исключение не отразится на решении, так как условие удаляется после того, как становится неактивным. В результате число строк не превысит
Пример 7.2. Применим приведенный алгоритм к задаче
L=2x1+x2max; 2x1+x2 7,5; 12x1+7x2 55; 5x1+2x2+х5 18; x1, x2 0, целые.
Умножаем 1-е неравенство на 2 и приводим все условия к равенствам:
4x1+2x2-x3 15; 12x1+7x2+x4 5;5 25x1+10x2+х5 90.
Решаем непрерывную задачу симплекс-методом. В табл. 7.3 представлено решение НЗ (оптимальная таблица выделена двойной рамкой, строка оценок записана первой для удобства расширения таблицы).
Базис
А0
А1
А2
А3
А4
А5
А6
j
8, 27
0
0
0
0
А2
0
1
0
-
0
А3
0
0
1
0
А1
1
0
0
-
0
А6
-
0
0
0
-
-
1
-
-
-
-
-
Решение содержит нецелые переменные. Наибольшую дробную часть имеет переменная x3. Выписываем соответствующую ей строку:
x3+ x4+ x5= . Из нее получаем 1-е условие отсечения x4+ x5 ,
которое приводим к равенству - x4- x5+x6= - .
Это равенство добавляем к оптимальной симплекс-таблице решенной НЗ с включением в число базисных вектора А6 (табл.7.3). К расширенной таблице применяем двойственный метод (направляющей является новая строка, направляющий столбец находится по ). Полученное решение, которое называют оптимальным относительно первого отсечения, приведено в табл. 7.4 (см. часть в двойной рамке).
Т
Базис
А0
А1
А2
А3
А4
А5
А6
А7
j
8, 2
0
0
0
0
0
0
А2
0
1
0
1
0
-
0
А3
0
0
1
0
0
1
0
А1
1
0
0
-
0
0
А5
0
0
0
1
-
0
А7
-
0
0
0
0
0
-
1
Оно также является нецелочисленным. Новое отсечение строим по переменной х2, имеющей наибольшую дробную часть. Выписываем уравнение
х2+х4 - х6= ,
из которого следует условие отсечения
х6
и затем равенство
х6 - х7= ,
добавляемое к последней симплекс-таблице (см. табл.7.4). Применяем двойственный симплекс-метод.
Полученное решение, оптимальное относительно второго отсечения, дано в табл. 7.5.
Таблица 7.5
Базис |
А0 |
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
А8 |
j |
8,0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
А2 |
|
0 |
1 |
0 |
1 |
0 |
0 |
- |
0 |
А3 |
|
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
А1 |
|
1 |
0 |
0 |
- |
0 |
0 |
|
0 |
А5 |
|
0 |
0 |
0 |
|
1 |
0 |
- |
0 |
А6 |
|
0 |
0 |
0 |
0 |
0 |
1 |
- |
0 |
А8 |
- |
0 |
0 |
0 |
- |
0 |
0 |
- |
1 |
Очевидно, что оно не удовлетворяет требованию целочисленности. Так как в базисное решение вернулась переменная x6, что означает строгое выполнение 1-го условия отсечения, соответствующие ей строка и столбец удаляются (отмечены выделением пунктирной полосой).
Теперь отсечение строим по переменной x1:
х1- х4+ х7 = х4+ х7 х4+ х7 – х8 = .
Добавляем полученное уравнение отсечения к последней таблице (табл. 7.5) и, используя снова двойственный метод, находим оптимальное решение расширенной НЗ (табл. 7.6). Это решение целочисленное и, следовательно, оно является оптимальным для исходной целочисленной задачи. ▲
И
Таблица 7.6
Базис
А0
L
8, 0
А2
6
А3
5
А1
1
А5
5
А4
1
Отмечается зависимость скорости сходимости от формы и порядка записи условий задачи, существенное влияние ошибок округления. Неприятной стороной алгоритма является постоянное увеличение числа строк вплоть до числа переменных в канонической форме. Если задача разрешима, алгоритм находит целочисленное решение только на последней итерации. Поэтому в случае прерывания расчета не будет получено ни одного даже приемлемого решения.
Эффективность алгоритма повышается с уменьшением значений аij и bi и заполненности матрицы условий А. Можно рекомендовать применение метода для задач небольшой размерности (до десятков переменных), когда значения аij и bi невелики и в оптимальном решении непрерывной задачи большая часть переменных имеет целые значения. Алгоритм мало пригоден для решения комбинаторных задач в целочисленной постановке.
Для других вариантов построения условий отсечения сходимость построенных на них алгоритмов не доказана, а отмеченные недостатки в основном не устраняются. Эти замечания относятся и к алгоритму отсечения для частично целочисленных задач.
В ряде пакетов прикладных программ метод отсечений применяется в комбинации с другими, точными или приближенными, методами.