Метод Гомори решения задач целочисленного программирования

Размещено на http://www.allbest.ru/

Сибирский федеральный университет

Метод Гомори решения задач целочисленного программирования

Соловьева Т.А.

Христофорова Е.И.,

научный руководитель:

доцент кафедры «Высшей математики - 3»

Климович Л.В.

Цель: изучить метод решения задач целочисленного программирования.

Объект исследования: задачи линейного программирования.

Предмет исследования: метод Гомори для решения задач целочисленного программирования.

Задачи:

1. изучить метод решения задач целочисленного программирования.

2. решить задачу целочисленного программирования методом Гомори.

В настоящее время нельзя назвать область человеческой деятельности, в которой не приходилось бы делать выбор. Многие задачи, с которыми приходится иметь дело, являются многовариантными. Среди множества рассматриваемых вариантов, мы привыкли принимать решение, исходя из здравого смысла, опыта или просто «на глаз». Однако это решение не всегда являлось верным, экономически выгодным и оптимальным. При современных масштабах производства даже незначительные ошибки оборачиваются громадными потерями. В связи с этим возникла необходимость применять для анализа определенные новые метода расчета. Такие методы объединили под общим названием «математическое программирование».

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

Нас будет интересовать линейное целочисленное программирование.

Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения.

Наиболее естественным классом практических задач, которые сводятся к задачам целочисленного программирования, являются задачи, в которых переменные -- физически неделимые величины (например, количество единиц какой-либо продукции: груз, оборудование).

Рассмотрим решение задачи целочисленного программирования методом Гомори на конкретном примере.

Задача. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19 м² площади. На приобретение оборудования предприятие может израсходовать 16 млн. руб., при этом оно может купить оборудование двух видов. Комплект оборудования I вида стоит 4 млн. руб., а II вида - 1 млн. руб. Приобретение одного комплекта оборудования I вида позволяет увеличить выпуск продукции в смену на 8 ед., а одного комплекта оборудования II вида - на 6 ед. Зная, что для установки одного комплекта оборудования I вида требуется 2 м² площади, а оборудования II вида - 5 м² площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет х₁ комплектов I вида и х₂ комплектов оборудования II вида. Тогда переменные х₁ и х₂ должны удовлетворять следующим неравенствам:

Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит

По своему экономическому содержанию переменные х_{1 и} х₂ могут принимать лишь целые неотрицательные значения, т.е.

Приведем систему ограничений к каноническому виду, прибавив дополнительные переменные х₃, х₄.

Метод Гомори (отсечения) решения задачи целочисленного программирования заключается в следующем. Сначала задачу надо решить без условия целочисленности. Если решение целочисленное (все требуемые компоненты задачи являются целыми числами), то задача решена. Если решение содержит нецелые компоненты, то в задаче необходимо ввести дополнительные ограничения.

Решим ее симплекс-методом без учета требования целочисленности (табл. 1).

Таблица 1

Все коэффициенты целевой функции при свободных переменных отрицательны, следовательно, найдено оптимальное решение: F_max= 376/9=41 при плане .

Среди компонент оптимального решения задачи имеются нецелые числа. Выбираем уравнение, для которого дробная часть свободного члена наибольшая.

; . Выбираем первое уравнение.

В общем виде это уравнение имеет вид:

Согласно этому уравнению составляется следующее неравенство (ограничение, отсечение):

Приведем уравнение к канонической форме и свободный член перенесем в правую часть.

Это уравнение присоединим к системе ограничений решенной задачи, т.е. составим новую таблицу Гаусса с дополнительным столбцом для нового неизвестного x_n+1, содержащую последний блок таблицы решенной задачи и новую строку, соответствующую построенному уравнению (табл. 2).

Таблица 2

Получили новое оптимальное решение: F_max = 41 при плане

Максимальная дробная часть свободного члена в последнем блоке соответствует первой строке, т.е. уравнению

Составим новое отсечение:

или уравнение

Новая рабочая таблица имеет вид:

Таблица 3

Новое оптимальное решение: F_max= 40 при плане

Таким образом, делаем еще три отсечения с целью получения целочисленного решения (табл. 4).

Таблица 4

Получен оптимальный целочисленный план: F_max = 36 при плане (3;2;3;2). Для нашей задачи достаточно было бы целочисленности только первых двух переменных.

Согласно данному решению предприятию необходимо приобрести 3 комплекта оборудования I вида и 2 комплекта II вида, что даст возможность максимально увеличить выпуск продукции до 36 единиц. Излишнюю площадь х₃ = 3 м² и полученную экономию денежных средств в размере х₄ = 2 млн. руб. можно использовать для извлечения дополнительной выгоды.

Таким образом, мы изучили метод решения задач целочисленного программирования. Методом Гомори решили конкретную задачу.

математический программирование целочисленный

Размещено на Allbest.ru