МЕТОДЫ РЕШЕНИЯ

ОДНОГО КЛАССА ТЕХНИКО-ЭКОНОМИЧЕСКИХ ЗАДАЧ

Сухов Я.И., Гарькина И.А.

Пензенский государственный университет архитектуры и строительства

Займемся определение максимального (минимального) значения линейной функции при ограничениях

- целые.

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

Составим математическую модель задачи. Предположим, что предприятие приобретает комплектов оборудования 1 вида и комплектов оборудования 2 вида. Тогда переменные и должны удовлетворять следующим неравенствам: .Если предприятие приобретет указанное количество оборудования, то общее увеличение продукции составит . По своему экономическому содержанию переменные и могут принимать лишь целые неотрицательные значения, то есть - целые. Многоугольник решений задачи, состоящей в определении максимального значения линейной функции f при выполнении заданных ограничений, приводится на рис.1.

Рис.1

Координаты всех точек многоугольника решений ОАВС удовлетворяют системе заданных линейных неравенств и условию не отрицательности переменных. Вместе с тем, условию целочисленности переменных удовлетворяют координаты лишь 12 точек, отмеченных на рис. 1. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF , который содержит все допустимые точки с целочисленными координатами и координаты каждой из вершин являются целыми числами. Значит, координаты точки максимума функции f на многоугольнике OKEMNF определяют оптимальный план задачи.

Построим вектор и прямую , проходящую через многоугольник решений OKEMNF. Прямую будем передвигать в направлении вектора до тех пор, пока она не пройдет через последнюю общую точку ее с данным многоугольником. Координаты этой точки и определят оптимальный план с максимальным значением целевой функции. В данном случае искомой является точка Е(1,3), в которой целевая функция принимает максимальное значение . В соответствии с этим планом, предприятию следует приобрести один комплект оборудования 1-го вида и три комплекта оборудования 2-го вида. Это обеспечит предприятию при имеющихся у него ограничениях на производственные площади и денежные средства максимальное увеличение выпуска продукции на 14 ед. в смену.

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

,

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

Приведенный пример с очевидностью подтверждает эффективность использования методов целочисленного программирования при решении ряда классов технико-экономических задач.