Метод Гомори
Целочисленные задачи линейного программирования. Метод Гомори
Методы отсечения. Метод Гомори
Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т. Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования. Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана. Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования. Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами: Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k -й строке симплексной таблицы записываем ограничение Гомори. Чтобы получить опорный план этой задачи, необходимо ввести в базис тот. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена. Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость. Если для дробного x j обнаружится целочисленность всех коэффициентов соответствующего уравнения строки , то задача не имеет целочисленного решения. Для приобретения нового оборудования предприятие выделяет 19 ден. Оборудование должно быть размещено на площади, не превышающей 16 кв. Предприятие может заказать оборудование двух видов: Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность. Тогда математическая модель задачи:. После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базис-. Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора. Введем вектор S 1. Получаем новый оптимальный нецелочисленный план. Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере-. В полученном плане максимальную дробную часть имеет компонента х 2 , поэтому записываем дополнительное ограничение по первой строке. План Х 5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке:. При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену. Полученную экономию денежных средств в размере 3 ден. На излишнюю площадь в 2 кв. Геометрическая интерпретация метода Гомори: FAQ Обратная связь Вопросы и предложения. Коломарова Решение задач линейного целочисленного программирования методом гомори. Задача линейного целочисленного программирования формулиру- ется следующим образом: МЕТОД ГОМОРИ Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Составленное ограничение добавляем к имеющимся в сим- плексной таблице, тем самым получаем расширенную задачу. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ГОМОРИ Задача: Тогда математическая модель задачи: Строим новое ограничение Гомори. Можно Определяем вектор, вводимый в базис: Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере- менной S 1. Определяем вектор, вводимый в базис: После проведения очередных симплексных преобразований получили: Дополнительное ограничение запишем по второй строке: Вектор, вводимый в базис: Соседние файлы в предмете Информатика Тынкевич Многошаговые процессы принятия решений динамическое программирование. Тынкевич Потоки в сетях и транспортная задача по критерию времени. Тынкевич Принятие решений в условия неопределенности теория игр и статистических решений. Тынкевич Решение транспортной задачи методом Данцига. Тынкевич Система Matlab Справочное пособие к курсу Численные методы анализа. Бияков Государственное образовательное учреждение высшего профессионального образования Кузбасский государственный технический университет. Бияков Графические нотации в стандарте IDEF0. Бияков Моделирование бизнес-процессов в стандарте IDEF0. Бияков Программа производственной практики. Ванеев Разработка инфологической модели базы данных. Составленное ограничение добавляем к имеющимся в сим-.
Сущность методов отсечения состоит в том, что сначала задача решается без условия целочисленности. Если полученный план целочисленный, задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами:. Дополнительное ограничение, обладающее указанными свойствами, называется правильным отсечением. Далее задача решается с учетом нового ограничения. После этого в случае необходимости добавляется еще одно ограничение и т. Геометрически добавление каждого линейного ограничения отвечает проведению прямой гиперплоскости , которая отсекает от многоугольника многогранника решений некоторую его часть вместе с нецелыми координатами, но не затрагивает ни одной из целых точек этого многогранника. В результате новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений и соответственно полученное при этом многограннике оптимальное решение будет целочисленным рис. Один из алгоритмов решения задачи линейного целочисленного программирования 6. Пусть задача линейного программирования 6. В этом случае можно доказать, что неравенство. Целой частью числа а называется наибольшее целое число , не превосходящее а. Дробная часть числа определяется как разность между этим числом и его целой частью, то есть. Для решения задачи целочисленного линейного программирования 6. Симплексным методом решить задачу 6. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования 6. Если первая задача 6. Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и по соответствующему уравнению системы 6. Полученную расширенную задачу решить симплексным методом. Если найденный оптимальный план будет целочисленным, то задача целочисленного программирования 6. В противном случае вернуться к п. Если задача разрешима в целых числах, то после конечного числа шагов итераций оптимальный целочисленный план будет найден. Если в процессе решения появится уравнение выражающее основную переменную через неосновные с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и данная задача не имеет целочисленного оптимального решения. Однако если все коэффициенты a ij , b i в 6. Полностью целочисленную задачу в каноническом виде можно получить также, если в 6. Для этого следует умножить 6. Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные. Основные переменные ; неосновные переменные. Переводим в основные переменные переменную х 2 , которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной х 2 , которое позволяет принять система ограничений, из условия минимума соответствующих отношений:. Переводим в основные переменные х 1 , , а в неосновные х 4. Базисное решение Х 3 оптимально для задачи , так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами. Однако решение Х 3 не удовлетворяет условию целочисленности 6. Обращаем внимание на то, что согласно 6. При этом для сокращения числа шагов итераций рекомендуется вводить дополнительное уравнение 6. Заметим, что после включения в систему ограничений дополнительного уравнения, соответствующего правильному отсечению, всегда будет получаться недопустимое базисное решение. Для получения допустимого базисного решения необходимо перевести в основные переменную, входящую с положительным коэффициентом в уравнение, в котором свободный член отрицательный, то есть х 4 или х 5 на этом этапе линейную функцию не рассматриваем. Переводим в основные, например, переменную х 5. Для геометрической интерпретации на плоскости 0 х 1 х 2 см. На стипендию можно купить что-нибудь, но не больше Методики проведения искусственной вентиляции легких C. Метод основан на измерении изменения частоты ультразвуковой волны при отражении ее от движущихся эритроцитов Corr: Вторичная группировка может осуществляться: Марксистско-ленинская философия - методологическая основа научной психологии I. Принципы и методы исследования современной психологии I. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? В противном случае к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: Графическая иллюстрация целочисленного решения Пусть задача линейного программирования 6. В этом случае можно доказать, что неравенство , 6.
Как завести бонусную карту ржд
Скайпарк в сочи как добраться из адлера
График отключения горячей воды 2017 год ярославль
Выписка из реестра федерального имущества образец
Инструкции по мытью игрушек в детском саду