Глава 1. Теория линейного программирования

1.1. Линейное программирование — инструмент исследования линейных моделей

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

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

В большом числе случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важная и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями. Сказанным определяется важность той роли, которую играет линейное программирование — метод отыскания условного экстремума линейной функции на множестве, заданном при помощи линейных соотношений типа равенств и неравенств (линейных ограничений) [1, с. 9].

Условия применимости линейной модели

Делимость. Если способ применяется с интенсивностями a и b (a < b), то его можно применять с любой интенсивностью x  [a; b].

Это условие не тривиально. Если, например, интенсивность выполнения работы измерять числом назначенных на нее работников, то допустимы только целые значения интенсивности. Если же интенсивность измеряется числом человеко-часов в сутки, то принцип делимости, по-видимому, выполнен.

Пропорциональность. Затраты, выпуски и полезность, производимые каждым способом, пропорциональны его интенсивности.

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

Аддитивность. Полезности и — для каждого ингредиента — затраты и выпуски, производимые всеми способами, суммируются.

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

Формы записи задач линейного программирования

В самом общем виде задача ЛП записывается следующим образом:

1 (1)

при

2 (2)

3 (3)

4 (4)

5 (5)

Определение 1. Матрица называется матрицей задачи (1) – (5). □

Более унифицированное представление задачи ЛП — стандартная форма:

при

для i  {1,…, m}, x  0.

Особенности стандартной формы: все переменные неотрицательны (n₁ = n), ограничения-равенства отсутствуют (m₁ = 0). Если ЦФ максимизируется, то m₂ = 0 и нет ограничений вида (3); в противном случае m₂ = m и нет ограничений вида (4). Полагая и , стандартную форму можно записать следующим образом:

6c  x  max (min) при Ax () b, x  0. (6)

Но самый простой вид имеет каноническая форма записи задач ЛП.

Определение 2. Задача (1) – (4) представлена в канонической форме, если все ограничения, кроме условий неотрицательности переменных, являются равенствами (m₁ = m) и все переменные неотрицательны (n₁ = n). □

Задача ЛП в канонической форме имеет, следовательно, вид

7c  x  max (min) при Ax = b, x  0. (7)

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

8c  x  max (min) при условиях Ax = b, и (5). (8)

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

Пусть a_ij — удельное (при единичной интенсивности) потребление ингредиента i технологическим способом j; a_ij < 0 означает, что способ j при единичной интенсивности производит | a_ij | единиц ингредиента i. Пусть , где x_j — интенсивность использования технологического способа j, c_j — его удельная (при единичной интенсивности) полезность. Из сформулированных выше свойств операции (делимость, пропорциональность, аддитивность) с очевидностью следует, что общая задача (1) – (5) принимает вид

9c  x  max при Ax  b, x  0. (9)

Это стандартная форма задачи ЛП. Здесь целевая функция описывает суммарную полезность плана х, левая часть ограничения  — это потребление ингредиента i при плане х. Смысл ограничения зависит от знака b_i. Неотрицательное b_i — это исходный запас ингредиента, и потребление не должно его превышать. Если же b_i < 0, то |b_i| интерпретируется как обязательство по поставке ингредиента вовне; при этом и левая часть неравенства должна быть отрицательной, а потребление в объеме d < 0 — это производство в объеме |d|. Ограничение в этом случае эквивалентно и требует, чтобы ингредиент был произведен в достаточном количестве.

Каждый столбец матрицы А дает технологическое описание некоторого способа деятельности системы, указывая в каких количествах потребляются/производятся все ингредиенты при единичной интенсивности способа. Соответствующий элемент вектора с (удельная полезность) добавляет к этому описанию экономическую компоненту.

Введем вектор переменных и перейдем к канонической форме задачи (9).

10c  x  max при (10)

11 для всех i; (11)

12x  0, s  0. (12)

Переменные s_i имеют ясный экономический смысл. Если b_i  0, то s_i — это неиспользованный при плане х остаток ингредиента i. Если же b_i < 0, то и по (9). Тогда есть объем производства ингредиента i сверх задания.

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

Свойства задач линейного программирования

Утверждение 1. Если задача Р разрешима и включает условие неотрицательности всех переменных (в частности, записана в стандартной или канонической форме), то среди ее оптимальных решений есть крайняя точка.

Доказательство в [9, стр. 132] □

Рассмотрим задачи, включающие условие неотрицательности всех переменных.

Определение 3. Строку i и столбец j матрицы А обозначим а_i и а ^j соответственно. Базис матрицы А — это любой набор из r(A) ее линейно независимых столбцов (базисных), где r(A) — ранг матрицы А. Удобно описывать базис упорядоченным списком базисных столбцов:  = (а ^j(i) |1 ≤ i ≤ r(A)), где j(i) — номер, который имеет в матрице А столбец, стоящий в списке на месте i. □

Рассмотрим совместную задачу линейного программирования Р в канонической форме (7) с матрицей А размерности m × n. Будем считать, что строки матрицы А линейно независимы, r(A) = m. Тогда каждый базис матрицы состоит из m столбцов. Для такой матрицы введем следующие определения.

Определение 4. Множество номеров базисных столбцов (для базиса ) будем обозначать N(), N() = { j(i) | 1 ≤ i ≤ m}.

Если базис фиксирован, то переменные задачи (7), соответствующие базисным столбцам, называются базисными.

Матрица В_, составленная из столбцов базиса  (в том порядке, в котором они входят в ), называется базисной матрицей, ее столбец номера i (обозначим его ) совпадает со столбцом номера j(i) в матрице .

Любой вектор xRⁿ относительно фиксированного базиса  = (a ^j(1),…,a ^j(m)) можно разбить на базисную часть х _б() = (х _j(1),…, x _j(m))  R^m и небазисную часть x _н() = (x_j |  j  N())  R^{n - m}. Порядок компонент в небазисной части вектора для нас не важен, но для определенности будем считать, что они упорядочены по возрастанию номеров j. □

Понятно, что базисная матрица — это невырожденная m×m-подматрица матрицы А. Зафиксируем базис . Предположим, что в него входят первые m столбцов матрицы А в порядке их номеров, т. е. j(i) = i для 1 ≤ i ≤ m. Этого всегда можно добиться перестановкой столбцов матрицы с соответствующим изменением порядка записи переменных в векторе х, что эквивалентно перестановке слагаемых в уравнениях задачи. Будем, однако, использовать исходные номера столбцов в матрице А как идентификаторы этих столбцов. Систему уравнений Ах = b можно записать в виде

13(В_ | М) ∙ х = В_ ∙ х_б() + М ∙ х_н() = b, (13)

где М — матрица размерности m ×(n – m). Заметим, что в строке матрицы А сначала записаны m элементов матрицы В_ , а затем n – m элементов матрицы М; в свою очередь, в столбце х верхние m элементов образуют вектор х_б(), а остальные — вектор х_н().

При х_н() = 0 система принимает вид В_ ∙ х_б() = b и имеет единственное решение . Это рассуждение является основанием для следующего определения.

Определение 5. Пусть  — произвольный базис матрицы А. Базисное решение системы уравнений Ах = b, порожденное базисом , — это вектор х такой, что и х_н() = 0; обозначается х^. □

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

Определение 6. Если базисная часть вектора х^ (равная по определению) неотрицательна, то  — допустимый базис, а х^ — базисное допустимое решение (БДР) задачи (7), порожденное этим базисом. □

Таким образом, небазисные компоненты БДР равны нулю, а столбцы матрицы А, соответствующие базисным компонентам, линейно независимы. Следовательно, столбцы, соответствующие положительным компонентам БДР, линейно независимы.

Замечание 1. Предположим, что БДР имеет k положительных компонент, которым соответствуют столбцы a ^j, j  N. Эти столбцы линейно независимы и r(A) = m, поэтому k ≤ m. Если k = m, то столбцы с номерами из N образуют единственный базис этого БДР. Если же k < m, то совокупность линейно независимых столбцов с номерами из N можно дополнить до допустимого базиса столбцами, соответствующими нулевым компонентам БДР. В этом и только этом случае в базисной части БДР будут нули. □

Определение 7. БДР х называют вырожденным, если в его базисной части есть нулевые компоненты, и невырожденным, если х_б() > 0.

Если х = х^ = х^ и   , то говорят, что базисное решение х имеет альтернативный базис. □

Утверждение 2. Если БДР имеет альтернативный базис, то оно вырожденно.

Доказательство в [9, стр. 135] □