Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов
При решении многих задач (планирование мелкосерийного производства, распределение кораблей по путям сообщения, выработка суждений типа "да-нет" и т. п.) нецелочисленное решение не имеет смысла. Попытка тривиального округления до целых значений приводит либо к нарушению ограничений задачи, либо к недоиспользованию ресурсов. Как мы имели возможность убедиться, для произвольной линейной программы (за исключением программ типа классической транспортной задачи, где коэффициенты матрицы ограничений равны 1 или 0) гарантировать целочисленность решения невозможно.
В случае двухмерной задачи проблема решается относительно просто путем выявления всех целочисленных точек, близких к границе множества планов, построения "выпуклой целочисленной оболочки" (выпуклого множества планов, содержащего все целочисленные планы) и решения задачи над этим множеством.
B общем случае выдвигается идея последовательного отсечения нецелочисленных оптимальных планов: обычным симплексным методом отыскивается оптимальный план и, если он нецелочисленный, строится дополнительное ограничение, отсекающее найденный оптимальный план, но не отсекающее ни одного целочисленного плана.
Эта идея, принадлежащая Д. Данцигу и Р. Гомори, впервые была представлена в форме дополнительного ограничения:
(сумма небазисных компонент оптимального плана должна быть отлична от нуля; хотя бы одна из небазисных компонент должна быть ненулевой). В самом деле, оптимальный план с нулевыми значениями небазисных компонент этому условию не удовлетворяет, что подтверждает отсечение этого плана от исходного множества.
К сожалению, для абсолютного большинства задач скорость сходимости процесса таких отсечений мала. Потому Р. Гомори предложена другая форма дополнительного ограничения. Так, если компонента плана, определяемая k-ым уравнением системы ограничений, нецелочисленна, то добавляется ограничение
Где fK - дробная часть компоненты плана (правой части ограничения) и fKj - дробная часть коэффициента при XJ (целая часть числа - наибольшее целое, не превышающее это число; дробная часть числа равна разности между числом и его целой частью), S* - новая дополнительная переменная.
Например, если ограничение имеет вид
То дополнительное ограничение принимает вид
Можно уменьшить объем преобразований, если руководствоваться следующими правилами:
- 1. выбирать в качестве базового для построения дополнительного ограничения уравнение, определяющее компоненту плана с наибольшей дробной частью; 2. для ввода в базис опорного плана расширенной задачи выбирать переменную, для которой достигается минимум из отношений абсолютных значений DJ к значениям fKj; 3. если одна из ранее введенных дополнительных переменных вошла в базис, ее и соответствующее ей уравнение можно отбросить (эта ситуация связана с появлением более жесткого условия, перекрывающего действие ранее введенного).
Появление дополнительного ограничения и дополнительной переменной вновь приводит к проблеме выбора начального опорного плана расширенной задачи и к использованию с этой целью искусственной переменной. Следует заметить, что если при поиске переменной, исключаемой из базиса, значениеQ (определяемое с учетом дополнительного ограничения) соответствует этому ограничению, то можно отказаться от использования искусственной переменной (она все равно выведется из базиса на этом же шаге решения).
Заметим, что для целочисленных программ может обнаружиться отсутствие целочисленных планов (противоречивость ограничений).
Для предложенного здесь метода доказана конечность процесса отсечений, но число этих отсечений непредсказуемо (вполне может обнаружиться быстрое решение задач с десятками переменных и ограничений и фантастически длительное для задач небольших размеров).
Похожие статьи
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Теория игр - Математическое моделирование экономических процессов
Одна из задач теории оптимальных решений - принятие решения в условиях неопределенности. Для обоснования решений разработаны специальные математические...
-
Календарный производственный программирование однооперационный Все существующие методы решения задач календарного планирования3 по степени достижения...
-
Элементы математических методов и моделей
Введение Основной целью данного курса является ознакомление студентов с основными математическими моделями и методами, используемых в процессах принятия...
-
Динамическое программирование - Математическое моделирование экономических процессов
В задачах линейного и нелинейного программирования экономический процесс считался статическим, т. е. не зависящим от времени, поэтому оптимальное решение...
-
Балансовые модели - Математическое моделирование экономических процессов
Балансовые модели предназначены для анализа и планирования производства и распределения продукции на различных уровнях - от отдельного предприятия до...
-
Ответ: В педагогических исследованиях прикладная направленность математики, понимается как содержательная и методическая связь курса математики с...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Как известно, человечество в своем стремительном развитии старается все более расширить сферы своей деятельности, сталкиваясь при этом с множеством новых...
-
Сетевое планирование и управление - Математическое моделирование экономических процессов
До появления сетевых методов планирования работ, проектов осуществлялось в небольшом объеме. Наиболее известным средством такого планирования был...
-
К числу приближенных методов оптимизации задач календарного планирования относятся: частичный и направленный перебор, метод Монте-Карло,...
-
Теория массового обслуживания - Математическое моделирование экономических процессов
Часто приходится сталкиваться с такими ситуациями: - очередь покупателей в кассах магазинов; - колонна автомобилей, движение которых остановлено...
-
Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
-
Геометрическая интерпретация - Математические методы и модели в экономике
Геометрическая интерпретация задачи линейного программирования является основой графического метода и применяется в основном при решении задач двумерного...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Метод конечных разностей -- широко известный и простейший метод интерполяции. Его суть заключается в замене дифференциальных коэффициентов уравнения на...
-
Изучив основные вопросы, связанные с календарным планированием, подведем итог. Задачи календарного планирования отражают процесс распределения во времени...
-
Известно, что проблема замены старого парка машин новыми, устаревших орудий -- современными -- одна из основных проблем индустрии. Оборудование со...
-
Задача Джонсона о двух станках Рассмотрим задачу последовательной обработки на двух машинах N различных деталей, если известно время Ai и Bi обработки...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Для достижения поставленной цели предприятию требуются материалы, оборудование, энергия, рабочая сила и другие ресурсы. Каждое предприятие такими...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Для того чтобы можно было составить план проведения численных экспериментов, необходимо определиться с выходными параметрами объекта, которые можно...
-
Рассмотрим две проблемы сравнительной оценки эффективности различных подходов к оптимизации управления экономическими системами. Сравнение по...
-
Методы построения решений по математическим моделям - Математическое моделирование в электромеханике
Системы дифференциальных уравнений, полученные для конкретных ти-пов электрических машин, содержат в скрытом виде исчерпывающую инфор-мацию о всех...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
Метод северо-западного угла - Математическое моделирование в менеджменте и маркетинге
Этап I. Поиск первого опорного плана . 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается...
-
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге
Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
-
Процесс экономико-математического моделирования - Экономико-математические методы
Этот процесс состоит из нескольких взаимосвязанных этапов. Разбиение на этапы и выделение на каждом этапе присущих ему процессов условно: на одном из...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Метод конечных элементов - МАтематическое моделирование в экономике
- Метод конечных элементов: триангуляция - Метод конечных элементов ( МКЭ ) -- численный метод решения задач прикладной механики. - Широко используется...
-
Модели и моделирование - Экономико-математические методы
Одним из основных методов научного познания является эксперимент, а самой распространенной его разновидностью - метод моделирования систем. В процессе...
-
Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения...
-
Заключение - Моделирование систем массового обслуживания с использованием метода Монте-Карло
Метод Монте-Карло можно определить как метод моделирования случайных величин с целью вычисления характеристик их распределений. Возникновение идеи...
-
Датой рождения метода Монте-Карло принято считать 1949 г., когда появилась статья под названием "The Monte Carlo method". Создателями этого метода...
-
Развитие методов многокритериальной оптимизации сложных систем обусловлено необходимостью повышения эффективности их функционирования на основе обобщения...
-
Программное управление Относительно просто может быть сформулирована так называемая задача программного управления. В ней предполагается, что управляющие...
-
В качестве примера конкретной модели процесса управления обсудим модель распределения времени между овладением знаниями и развитием умений, впервые...
-
Моделирование процессов управления предполагает последовательное осуществление трех этапов исследования. Первый - от исходной практической проблемы до...
-
Важнейшие математические модели обычно обладают важным свойством Универсальности : принципиально разные реальные явления могут описываться одной и той же...
Метод Гомори последовательных отсечений - Математическое моделирование экономических процессов