Целочисленные задачи линейного программирования. Метод Гомори

Яндекс.Директ Все объявленияЯ изучила работу в Ворд и Эксель! Делюсь своим секретом...wq3.ru  Программирование, скидки до 90% Мы собрали все скидки до 90% на программирование. Выбери свою скидку!kuponator.ru Самара

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

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

Пример 20.

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

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

(70)

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

(71)

По своему экономическому содержанию переменные x₁ и  могу принимать лишь целые неотрицательные значения, т. е.

(72)

x₁,  – целые. (73)

Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (71) при вы полнении условий (70), (72) и (73). Так как неизвестные могут принимать только целые значения, то задача (70) – (73) является задачей целочисленного программирования. Поскольку число неизвестных задачи равно двум, решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для этого прежде всего построим многоугольник решений задачи, состоящей в определении максимального значения линейной функции (71) при выполнении условий (70) и (72) (рис. 11). Координаты всех точек построенного многоугольника решений ОАЕВС удовлетворяют системе линейных неравенств (70) и условиюнеотрицательности переменных (72). Вместе с тем условию (73), т. е. условию целочисленностипеременных, удовлетворяют координаты лишь 12 точек, отмеченных на рис. 11. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВСмногоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (71) на многоугольнике OKEMNF, то координаты этой точки и определят оптимальный план задачи.

Для этого построим вектор  и прямую  проходящую через многоугольник решенийOKEMNF (число 12 взято произвольно). Построенную прямую передвигаем в направлении вектора  до тех пор, пока она не пройдет через последнюю общую точку ее с данным многоугольником. Координаты этой точки и определяют оптимальный план, а значение целевой функции в ней является максимальным.

В данном случае искомой является точка E(1; 3), в которой целевая функция принимает максимальное значение  Следовательно, координаты точки Е определяют оптимальный план задачи (70) – (73). В соответствии с этим планом предприятию следует приобрести один комплект оборудования 1 вида и три комплекта оборудования II вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуск продукции, равное 14 ед. в смену.