Задачи линейного программирования

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

Если число переменных равно двум, то задача имеет простое графическое (геометрическое) решение.

Пусть требуется найти оптимальное значение функции

при ограничениях:

.

Неравенство определяет на плоскости полуплоскость. Для ее определения построим границу полуплоскости – прямую (удобнее всего ее строить по точкам пересечения с осями координат). Чтобы определить, какую из полуплоскостей надо взять, берется произвольная точка вне прямой (чаще всего точка ) и ее координаты подставляются в неравенство. Если неравенство выполняется, то берут полуплоскость, содержащую точку ; если не выполняется – не содержащую точку . Область, полученная пересечениями полуплоскостей, определенных для каждого из неравенств системы (1.5.1), (1.5.2), и лежащая в первой четверти, и есть область допустимых значений.

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

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

Пример. Завод может производить два вида болтов для крепления колес автомобилей. Для каждого вида болтов должно последовательно использоваться четыре разных группы оборудования, имеющегося в следующих количествах: оборудования группы А – 24, группы В – 16, группы С – 32, и группы D – 24 единицы.

При существующей на заводе технологии, на производство единицы продукции первого вида требуется занять: оборудования группы А – 2, группы В – 1, С – 4 и группы D – 0 единиц.

Техническими коэффициентами при производстве продукции второго вида будут 2, 2, 0 и 4.

Известно, что единица продукции первого вида дает заводу прибыль 4руб., а второго – 6руб. Сколько единиц продукции каждого вида должен производить завод, чтобы получить наибольшую прибыль?

Запишем исходные данные задачи в форме таблицы.

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

, .

Целевая функция будет иметь следующее выражение:

.

Теперь наша задача математического программирования имеет законченный вид.

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

Построим многоугольник допустимых решений (рис.1.5.2).

Проведем в системе координат прямые, координаты точек которых характеризуют максимальное использование оборудования всех групп: , , , . Взяв какую-нибудь точку, например, начало координат, установим, какую полуплоскость определяет соответствующее уравнению неравенство. В результате пересечения полуплоскостей получим некоторый многоугольник , представляющий собой геометрическое место точек, координаты которых определяют возможный при данных условиях производства вариант плана выпуска продукции. Любая точка, лежащая за пределами многоугольника , своими координатами покажет невозможность выполнения такого плана, так как он не будет обеспечен необходимым производственным оборудованием.

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

Найдем точку области допустимых решений, координаты которой соответствуют оптимальному решению, графическим путем. Для этого строим нормальный радиус-вектор или вектор меньшей длины , координаты которого пропорциональны координатам вектора , и через точку проводим прямую, перпендикулярную ему. Построенную прямую перемещаем параллельно самой себе в направлении вектора . Прямые, параллельные первоначально полученной прямой , называются линиями уровня доходности. Удаляясь от начала координат в направлении вектора , то есть увеличивая значение целевой функции, можно найти такую прямую, которая будет касаться только одной вершины выпуклого множества возможных решений. Очевидно, что будет вершина многоугольника, наиболее удаленная от линии уровня. Координаты этой вершины и покажут оптимальное решение задачи на .

Из рис. 1.5.2 следует, что опорной, по отношению к многоугольнику решений , эта прямая становится в точке , где функция принимает максимальное значение. Точка лежит на пересечении прямых и . Координаты точки определяются из решения системы этих уравнений.

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

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