Начальным этапом решения задачи целочисленного линейного программирования - / Н.Ю. Коломарова Решение задач линейного целочисленного программирования методом гомори

Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т. Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования.

Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Сущность метода заключается в построении ограничений, отсекающих нецелочисленные решения задачи линейного программирования, но не отсекающих ни одного целочисленного плана.

Рассмотрим алгоритм решения задачи линейного целочисленного программирования этим методом. Решаем задачу симплексным методом без учета условия целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования. Если обнаруживается неразрешимость задачи, то и неразрешима задача целочисленного программирования.

Если среди компонент оптимального решения есть нецелые, то к ограничениям задачи добавляем новое ограничение, обладающее следующими свойствами: Для построения ограничения выбираем компоненту оптимального плана с наибольшей дробной частью и по соответствующей этой компоненте k -й строке симплексной таблицы записываем ограничение Гомори.

Чтобы получить опорный план этой задачи, необходимо ввести в базис. Решаем при помощи обычных симплексных преобразований полученную задачу. Если решение этой задачи приводит к целочисленному оптимальному плану, то искомая задача решена.

Целочисленная задача ЛП

Если мы получили нецелочисленное решение, то снова добавляем одно дополнительное ограничение, и процесс вычислений повторяется. Проделав конечное число итераций, либо получаем оптимальный план задачи целочисленного программирования, либо устанавливаем ее неразрешимость. Если для дробного x j обнаружится целочисленность всех коэффициентов соответствующего уравнения строкито задача не имеет целочисленного решения.

Для приобретения нового оборудования предприятие выделяет 19 ден. Оборудование должно быть размещено на площади, не превышающей 16 кв. Предприятие может заказать оборудование двух видов: Требуется составить оптимальный план приобретения оборудования, обеспечивающий максимальную общую производительность.

Тогда математическая модель задачи:.

МЕТОД ОТСЕЧЕНИЙ ГОМОРИ — Мегаобучалка

После построения дополнительного ограничения имеем новую задачу линейного программирования, в которой 3 ограничения. Для получения опорного плана этой задачи необходимо найти третий базис. Получили задачу, в которой 4 ограничения, следовательно, в базисе должно быть 4 единичных вектора. Введем вектор S 1. Получаем новый оптимальный нецелочисленный план.

Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере. В полученном плане максимальную дробную часть имеет компонента х 2поэтому записываем дополнительное ограничение по первой строке. План Х 5 - оптимальный нецелочисленный. Дополнительное ограничение запишем по второй строке:.

При этом будет достигнута максимальная производительность работы оборудования, равная 36 т продукции за смену.

Целочисленная задача ЛП — Студопедия

Полученную экономию денежных средств в размере 3 ден. На излишнюю площадь в 2 кв. Геометрическая интерпретация метода Гомори: FAQ Обратная связь Вопросы и предложения. Коломарова Решение задач линейного целочисленного программирования методом гомори. Задача линейного целочисленного программирования формулиру- ется следующим образом: МЕТОД ГОМОРИ Одним из методов решения задач линейного целочисленного программирования является метод Гомори. Составленное ограничение добавляем к имеющимся в сим- плексной таблице, тем самым получаем расширенную задачу.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ МЕТОДОМ ГОМОРИ Задача: Тогда математическая модель задачи: Строим новое ограничение Гомори.

Можно Определяем вектор, вводимый в базис: Учитывая замечание 1, вычеркиваем строку и столбец, соответствующие пере- менной S 1. Определяем вектор, вводимый в базис: После проведения очередных симплексных преобразований получили: Дополнительное ограничение запишем по второй строке: Вектор, вводимый в базис: Соседние файлы в предмете Информатика Тынкевич Многошаговые процессы принятия решений динамическое программирование.

Тынкевич Потоки в сетях и транспортная задача по критерию времени. Тынкевич Принятие решений в условия неопределенности теория игр и статистических решений. Тынкевич Решение транспортной задачи методом Данцига. Тынкевич Система Matlab Справочное пособие к курсу Численные методы анализа.

Бияков Государственное образовательное учреждение высшего профессионального образования Кузбасский государственный технический университет. Бияков Графические нотации в стандарте IDEF0. Бияков Моделирование бизнес-процессов в стандарте IDEF0.

Бияков Программа производственной практики. Ванеев Разработка инфологической модели базы данных. Составленное ограничение добавляем к имеющимся в сим.

  • Советуем скачать
Прежде чем выполнять очередную итерацию, необходимо проверить, оптимально ли наше решение?
Исходная задача решается как обычная задача ЛП, без соблюдения условия целочисленности.