Представленный ниже целочисленный алгоритм обладает следующими свойствами: - Целочисленное программирование
- 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования.
Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперплоскостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.
Обычно в ограничения задачи (2) включаются в тривиальные соотношения xj= - (-Xj) (j'=1,..., n), а задача в матричной форме принимает вид:х = А (-хn), (3)
Где х - вектор-столбец с компонентами Х 0, x1,..., xn, xn+1,..., xn+m А - соответствующая матрица размера (п + т + 1) * (n + 1) и (-хn) - вектор с компонентами (1, - x1, - x2,..., - xn), представляющими собой небазисные переменные исходной таблицы. Задачу целочисленного программирования также можно записать в виде таблицы.
Причины представления переменных в виде (-x1), (-x2,......, (-xn)) - чисто исторические, но это стало обычной практикой в целочисленном программировании. Будем использовать бj(j = 0, 1,..., п) для обозначения j-го столбца текущей таблицы и aij (i = 0, 1,..., п + т; j = 0, 1,..., n) для обозначения элемента 1-й строки и 7-го столбца таблицы. Предполагается, что все a, ij в исходной таблице целые. Следовательно, все слабые переменные xn+1,..., Хn+m должны быть также неотрицательными целыми числами.
При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочисленного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма аij?0 (i = 1,......, п + т) и a0j? 0 (j' = 1,..., n). (Для получения исходного двойственного допустимого решения введем дополнительное ограничение xn+m+1 == М - X1 - x2 - ... - xn? 0, где M - достаточно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если аi0? 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если аi0? 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е. аi0<О для i == п + т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi0? 0. Если аi0 получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi0 (i = 1,..., n,..., n + m) не станут все целыми и неотрицательными.
Если после введения дополнительного ограничения текущая таблица перестает быть прямо допустимой, то текущее решение, представляющее собой вершину многогранника решений, не удовлетворяет этому дополнительному ограничению. Другими словами, дополнительное ограничение отсекает часть пространства решений. Если дополнительные ограничения не отсекают ни одной целочисленной точки пространства решений исходной задачи, то, вполне вероятно, после введения достаточного числа дополнительных ограничений вершины суженного множества решений будут целочисленными. Тогда, используя симплекс-метод, можно получить оптимальное целочисленное решение. Трудность состоит в систематическом получении дополнительных ограничений и доказательстве конечности алгоритма.
Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таблица также меняется. Будем использовать t для обозначения t-й. таблицы. Матричное уравнение (3) запишется как
Хt = Аt (-хtn), (4)
Где х° - вектор-столбец с n + т + 1 компонентами, А° - матрица размера (п + т + 1)*(n + 1) и (-х 0n) - вектор с компонентами (1, - x1,..., - xn), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а 0i?0 (j = 1,..., n), а 00 ? 0 (mod 1) 1} и аi0 ? 0 (i=1,..., п+т) - целые неотрицательные числа, то получено оптимальное решение целочисленной задачи. Если аi0 не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (4), в котором аi0m нецелое. Опуская индексы строки, имеем
X=a0+?aj(-xj) (5)
Где xj в правой части - текущие небазисные переменные и a0 - нецелое. Поскольку требуется, чтобы х было целым, или х ?0 (mod1), правая часть уравнения (5) также должна удовлетворять условию
0?a0+?aj(-xj) (mod1). (6)
Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы xj, были целыми, можно алгебраически складывать с отношения 0?f0+?jfi(-xi) (mod1) (0<f0<1, 0?fj<1).
Похожие статьи
-
Метод ветвей и границ, Ветку считают тупиковой, если: - Целочисленное программирование
Впервые метод ветвей и границ был предложен Ландом и Дойгом в 1960 году для решения общей задачи целочисленного линейного программирования (Land A. H.,...
-
Циклический алгоритм целочисленного программирования - Целочисленное программирование
Рассмотрим следующую задачу линейного программирования: Максимизировать X0=a00-a01x1-a02x2-........-a0nxn, (2) При условии:...
-
Какими свойствами обладают алгоpитмы - Основы программирования
Основные свойства алгоритмов следующие: 1. Понятность для исполнителя -- исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея...
-
Что такое алгоритм - Основы программирования
Человек ежедневно встречается с необходимостью следовать тем или иным правилам, выполнять различные инструкции и указания. Например, переходя через...
-
Введение - Целочисленное программирование
При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных. Такие...
-
Свойства алгоритмов - Алгоритм
Данное выше определение алгоритма нельзя считать строгим - не вполне ясно, что такое "точное предписание" или "последовательность действий,...
-
Целочисленное программирование. Основные понятия. - Целочисленное программирование
При рассмотрении целого ряда задач финансового менеджмента и бизнеса необходимо учитывать требование целочисленности используемых переменных. Такие...
-
Решение задачи, Анализ оптимального решения - Использование методов линейного программирования
1. Для задания необходимых параметров оптимизации нажатием кнопки Параметры откроем окно "Параметры поиска решения" (рис.4). В этом окне оставьте...
-
Как записываются алгоритмы на школьном алгоритмическом языке - Основы программирования
Основные служебные слова Алг (алгоритм) Сим (символьный) Дано Для Да Арг (аргумент) Лит (литерный) Надо От Нет Рез (результат) Лог (логический) Если До...
-
Введение, РЕКУРСИЯ - Рекурсивное программирование
Основой для разработки рекурсивных алгоритмов служат, так называемые, Рекуррентные соотношения (формулы), устанавливающие зависимость между результатами...
-
Теоретическая основа линейного программирования, Симплекс метод - Линейное программирование
Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного...
-
Постановка задачи Постановка практической задачи ЛП включает следующие основные этапы: - определение показателя эффективности, переменных задачи, -...
-
Что такое графический способ записи алгоритмов - Основы программирования
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. Такое графическое представление называется...
-
Рисунок 6 - Трубная цилиндрическая резьба с допусками. Координаты точек отображены в таблице 1 приложения Д Копирование построенной резьбы: Выделяем...
-
Что такое "Исполнитель алгоритма" - Основы программирования
Исполнитель алгоритма -- это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия,...
-
Разложение Фурье, основные свойства - Один алгоритм сжатия изображения
Теория рядов Фурье наиболее просто строится в пространстве т. е. на множестве функций, для которых сходится интеграл от ее квадрата, В пространстве...
-
Геометрический метод, Двойственная задача - Линейное программирование
Применяется для задач с двумя переменными. Метод решения состоит в следующем: На плоскости строятся прямые, которые задают соответствующие ограничения:...
-
Методика решения задач ЛП графическим методом - Линейное программирование
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. II. Найти и заштриховать...
-
Разработка алгоритма головной программы Схема алгоритма головной программы описывает общий сценарий работы разрабатываемого приложения. В составе проекта...
-
Математический аппарат Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования,...
-
В основе алгоритма лежит численное исследование пространства управляемых параметров редуктора. Процесс поиска оптимального решения выполняется за четыре...
-
"РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT EXCEL" Цель работы Приобретение навыков решения задач линейного программирования...
-
Силовые алгоритмы для иерархически-кластеризованных графов - Визуализация графа цитирования
На данный момент мы рассмотрели алгоритм для отрисовки некластеризованных графов и их улучшения. Теперь необходимо изучить подходы, которые используются...
-
Результаты расчета (точки искомой функции) сохраняются в переменных-массивах: для аргумента X и функции Y, которые отображаются в виде таблицы или...
-
Модификации алгоритма Лемпеля-Зива, предложенная Терри Уэлчем - Анализ алгоритма Лемпеля-Зива
В 1984 году Терри Уэлч (Terry Welch) предложил адаптивный сброс словаря для алгоритма LZ78 [3]. В этом случае при заполнении словаря сброс словаря не...
-
Аннотация В статье рассматриваются два способа уменьшения времени вычисления дерева решений для задач линейного параметрического программирования с...
-
Признак оптимальности плана перевозок T. З. устанавливает теорема. Теорема. Для того, чтобы некоторый допустимый план X = (xij)m-nT. З. был оптимальным,...
-
Самым традиционным и широко известным из структурированных типов данных является массив (иначе называемый регулярным типом) - однородная упорядоченная...
-
Цель Работы - научиться использовать операции динамического выделения и освобождения памяти на примере работы с одномерными и двумерными массивами, а...
-
- установить свойство Align в значение AlBottom ; - выбрать свойство Panels и с помощью кнопки в левом верхнем углу разбить панель на две части (рисунок...
-
Возможны случаи, когда внутри тела цикла необходимо повторять некоторую последовательность операторов, т. е. организовать внутренний цикл. Такая...
-
Алгоритм работы декодера кода Рида - Маллера будем разрабатывать на основе уже приведенных выше уравнений. Алгоритм приведен на рисунке 12. В начале...
-
Значения свойств объектов можно менять двумя способами: При проектировании : В каждый момент проектирования только один объект является выделенным...
-
Наш интернет-магазин реализуем с использованием языка гипертекстовой разметки html, языка программирования php и СУБД MySQL. Главная часть...
-
Строгая типизация - Основные свойства функциональных языков программирования
Практически все современные языки программирования являются строго типизированными языками (возможно, за исключением языка JavaScript и его диалектов, не...
-
ОПЕРАТОР ВВОДА ДЛЯ ЧТЕНИЯ ФАЙЛА, ОПЕРАТОР ВЫВОДА - Язык программирования Паскаль
Оператор ввода для чтения файла обладает всеми свойствамии обычного оператора READ. Вкачестве параметров могут быть переменные; каждая переменная поучает...
-
Это задача оптимизации, в которой переменные принимают только два значения: "единица - ноль". Пример - задача "коммивояжера". Цель работы: минимизировать...
-
В этом разделе намеренно допущено отступление от общей методики - не смешивать разные компоненты. Это сделано для облегчения демонстрации построения...
-
Общий алгоритм принятия решений, Игра на префлопе - Разработка покерного робота
В данной главе будет рассказано об основных подходах, которые были применены для разработки стратегии покерного агента. Игра на префлопе Для игры на...
-
Описание алгоритма - Решение системы линейных уравнений методом Гаусса
Согласно заданию необходимо разработать программу для решения линейных уравнений методом Гаусса. Поскольку данная программа является приложением Windows,...
Представленный ниже целочисленный алгоритм обладает следующими свойствами: - Целочисленное программирование