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

В настоящее время линейное программирование используется в самых различных областях (планирование, управление, военное дело, экономика и т. д.). Для некоторых задач, обладающих специфическими особенностями (например, транспортная задача), разработаны специальные методы решения, более эффективные, чем симплекс-метод [8, 23]. В качестве примера мы рассмотрим только несколько задач, которые сводятся к линейному программированию. Некоторые из этих задач, или близкие к ним по постановке уже рассматривались в разд. 2.4.

Задача выбора (назначения)

Имеется п различного рода работ А_ь Аг, А_п и столько же механизмов (способов) их выполнения В_ь В2, ..., В_п. Каждый механизм с известной производительностью может выполнить любую работу, но будет выполнять только одну. Пусть заданы величины Су, которые являются оценками производительности (эффективности) механизма В при выполнении работы Aj. Вектор-строка Сц, Cj2, ..., Cj_n, характеризует качество i-ro механизма. Естественно стремиться к такой расстановке механизмов, чтобы суммарный эффект (производительность) был максимален. Таким образом, для каждого механизма нужно выбрать работу (или для каждой работы механизм) с наибольшим суммарным эффектом.

Математически это означает следующее. Задана квадратная матрица

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

При условии jk Ф j_m при к ф ш. Здесь к — номер строки, a — номер столбца выбранного элемента.

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

Введем переменные: Ху = 1, если элемент су выбран, и Ху = О, если этот элемент не выбран (i, j = 1,2, ..., n).

Целевая функция примет вид:

При условии для всех i = 1,2, ..., п.

Это условие означает, что каждый механизм используется только на одной работе. Нужно еще условие:

Это условие означает, что каждую работу выполняет только один механизм. И, конечно, нужны неравенства 0 < ху< 1. Мы получили задачу целочисленного линейного программирования, в которой число переменных равно п², а число ограничений — равенств равно 2п плюс двусторонние ограничения-неравенства на каждую переменную. Характерная особенность данной задачи состоит в том, что о требованиях целочисленности можно забыть, они выполняются автоматически.

Если заданы не производительности механизмов при выполнении работ, а затраты (стоимости), в наших рассуждениях ничего не меняется, но вместо максимума нужен минимум. Наша задача записана в несколько необычной форме: вместо вектора коэффициентов целевой функции у нас матрица су и вместо вектора неизвестных матрица Ху. Это так называемая двухиндексная задача.

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