ПОСТАНОВКА ЗАДАЧИ. ГЕОМЕТРИЧЕСКИЙ МЕТОД РЕШЕНИЯ


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

 

(2.1.1)

 

Здесь целевая функция представляет собой скалярное произведение

 

(2.1.2)

 

векторов и , – матрица размерности :

 

, (2.1.3)

 

– вектор-столбец: (T – символ транспонирования),

– n-мерное вещественное линейное пространство. Векторы , и матрица известны. Требуется найти хотя бы один вектор , принадлежащий допустимому множеству задачи (2.1.1)

 

,

 

доставляющий максимум функции (функционалу) .

В дальнейшем (в зависимости от контекста) наряду с термином «вектор x» будет также использоваться термин «точка x», так как координаты точки x совпадают с координатами вектора, проведенного в эту точку из начала координат, а именно такие вектора и будут иметься в виду.

Помимо варианта записи задачи (2.1.1) существуют другие способы формулировки задач линейного программирования. Так называемая стандартная задача линейного программирования записывается в виде:

 

(2.1.4)

 

Существует также каноническая задача линейного программирования. Ее формулировка имеет вид:

 

(2.1.5)

 

В выражениях (2.1.4), (2.1.5) условие отсутствует, однако подразумевается как само собой разумеющееся. Покажем, что постановки (2.1.1), (2.1.4) и (2.1.5) можно свести одну к другой. Сначала преобразуем (2.1.4) и (2.1.5) к виду (2.1.1), затем (2.1.1) – к виду (2.1.4), а (2.1.4) – к виду (2.1.5). Из этого будет следовать, что (2.1.1) сводится к виду (2.1.5).

В задаче (2.1.4) условие запишем в виде , где – единичная матрица размерности . Сформируем матрицу размерности и вектор размерности :

 

, .

 

Тогда задача (2.1.4) запишется в виде, представляющем собой полную аналогию задачи (2.1.1):

 

(2.1.6)

 

В задаче (2.1.5) условие представим в виде системы неравенств:

 

 

а условие – в виде . Сформируем матрицу размерности и вектор размерности :

 

, .

 

В результате задача (2.1.5) примет вид (2.1.6), т.е. будет сформулирована в виде основной задачи (2.1.1).

Теперь покажем, как основная задача (2.1.1) сводится к стандартной, т.е. к виду (2.1.4). Представим вектор в задаче (2.1.1) в виде разности векторов и :

 

, , , , .

 

Запись означает, что все координат вектора неотрицательны. Тогда задача (2.1.1) запишется в виде:

 

(2.1.7)

 

Введем матрицу размерности , а также векторы и , размерность каждого из которых равна :

 

, ,

 

Это позволяет записать задачу (2.1.7) в виде:

 

 

что полностью соответствует стандартной задаче (2.1.4).

Теперь рассмотрим, как стандартная задача (2.1.4) может быть сведена к канонической, т.е. к виду (2.1.5). Введем переменную , и запишем задачу (2.1.4) в виде:

 

(2.1.8.)

 

Далее введем матрицу размерности , а также векторы и , каждый из которых имеет размерность :

 

, , .

 

Тогда (2.1.8) примет вид:

 

 

что полностью соответствует канонической задаче (2.1.5).

 

Пример 2.1.1. Привести к каноническому виду следующую задачу:

 

 

Сначала преобразуем задачу к стандартному виду. Для этого прежде всего перепишем ее в виде:

 

 

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

 

 

Заменив переменную разностью новых переменных, получим задачу в стандартном виде:

 

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

 

 

Рассмотрим задачу (2.1.5), в которой ранг r матрицы A (см. (2.1.3)) равен m. Если при этом выполнено условие , то такую задачу можно решать геометрически. Для этого сначала необходимо выбрать две свободные переменные и выразить через них все остальные переменные. Например, если в качестве свободных переменных выбрать и , то получим:

 

(2.1.9)

 

.

Числа рассчитываются через элементы матрицы A и компоненты вектора b ( ), числа , кроме того, через компоненты вектора c ( ). Таким образом, задача от n переменных сводится к задаче от двух переменных и , решив которую, остальные переменные легко могут быть найдены по формулам (2.1.9).

 

Запишем задачу в виде:

 

(2.1.10)

 

где

 

Покажем, что константу в задаче (2.1.10) можно не учитывать, так как

она влияет только на значение самого максимума, но не влияет на значение искомой точки максимума. Для этого рассмотрим задачу общего вида множество решений которой

 

 

Рассмотрим также задачу где с множеством решений . Нетрудно убедиться в том, что . Действительно, и справедливо неравенство , которое равносильно неравенству . Следовательно, каждый элемент множества принадлежит множеству . Обратное утверждение доказывается аналогично. Итак, вместо задачи (2.1.10) можно решать задачу

 

(2.1.11)

 

Решение задачи (2.1.11) может быть найдено геометрическим методом, применение которого продемонстрируем на конкретном примере.

Пример 2.1.2

 

 

Данная задача является канонической, ;

 

, , , ,

 

– целевая функция.

Выбрав и в качестве свободных переменных, из системы находим:

 

(2.1.12)

 

Подстановка этих выражений в целевую функцию дает:

 

Отбросив константу -38, сформулируем задачу для двух переменных и :

 

(2.1.13)

 

Неравенства в этой задаче образуют систему, графическое решение которой представляет собой пятиугольник ABCDE, показанный на рис. 2.1.1. Это и есть допустимое множество решений рассматриваемой задачи линейного программирования. Рассмотрим уравнение

 

(2.1.14)

 

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

C
B
A
D
E

ется в направлении вектора с координатами (6,15), сохраняя ортогональность с этим вектором. На рис. 2.1.1 показано конечное положение прямой (2.1.14), при котором ее пересечение с пятиугольником ABCDE не пусто. Оно соответствует значению , при этом пересечением является точка C. Решением задачи (2.1.13) являются координаты точки C: , . Их подстановка в выражения (2.1.12) позволяет найти значения остальных координат искомого решения исходной задачи: , .

Запишем найденное решение в виде: . При этом .

СИМПЛЕКС-МЕТОД

Название «симплекс-метод» связано с тем, что он впервые разрабатывался применительно к задачам линейного программирования, в которых допустимое множество представляло собой симплекс:

 

 

Другое название симплекс-метода – метод последовательного улучшения плана.

Рассмотрим каноническую задачу линейного программирования:

 

(2.2.1)

 

Допустимое множество задачи (2.2.1) может быть задано выражением:

 

. (2.2.2)

 

Столбцы матрицы размерности образуют -мерные векторы

 

,…, ,…, ; (2.2.3)

 

Условие в (2.2.1), , означает, что Рас-

смотрим множество

 

, (2.2.4)

т.е. множество, состоящее из индексов при положительных координатах вектора . Тогда

 

.

 

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

Точка называется опорной точкой в задаче (2.2.1), если векторы линейно независимы.

Справедливы следующие утверждения:

1) если в задаче (2.2.1) множество не пусто, то оно имеет опорные точки и число их конечно;

2) если множество решений задачи (2.2.1) не пусто, то оно содержит хотя бы одну опорную точку из множества .

 

Пример 2.2.1. Найти опорные точки и решение задачи:

 

Здесь , , ,

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

 

(2.2.5)

 

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

Рассмотрим набор . В этом случае система (2.2.5) имеет вид:

– решений нет.

Такой же результат дает рассмотрение наборов . Это означает, что ни один из столбцов матрицы не коллинеарен вектору . Рассмотрим набор . В этом случае система (2.2.5) может быть записана в виде:

 

и имеет решение

 

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

 

Ее решение содержит отрицательное значение, поэтому опорную точку в данном случае сформировать невозможно. Перейдем к рассмотрению набора . Система уравнений типа (2.2.5) в этом случае имеет вид:

 

 

Ее решение позволяет сформировать опорную точку , в которой Действуя аналогичным образом, для оставшихся наборов получаем следующие результаты:

 

– дает опорную точку , в которой ;

 

– не позволяет сформировать опорную точку, так как решение системы уравнений содержит отрицательное значение;

 

– дает опорную точку , в которой

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

 

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

Пусть любые векторов из векторов (2.2.3) линейно независимы. Тогда число случаев, которые необходимо рассмотреть при фиксированном , составит

 

(2.2.6)

 

В рассмотренном выше примере 2.2.1 Для вычисления факториала при больших значениях можно воспользоваться приближенным выражением, полученным из формулы Стирлинга:

 

 

Тогда, считая значения и также большими, из (2.2.6) получим:

.

Например, при получим

 

 

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

 

.

 

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

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

Опорная точка (см. (2.2.2)) называется невырожденной, если

 

(2.2.7)

 

(мощность множества равна ). Если в задаче линейного программирования (2.2.1) все опорные точки невырождены, то задача называется невырожденной. Симплекс-метод будем рассматривать применительно к невырожденным задачам. Вырожденная задача может быть сведена к невырожденной путем алгебраических преобразований.

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

1) является решением задачи (2.2.1);

2) задача (2.2.1) не имеет решений;

3) рассчитывается следующая опорная точка , причем

>

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

Поскольку – опорная точка и задача невырождена, столбцы линейно независимы и выполнено (2.2.7). Столбцы образуют базис в . Разложение произвольного вектора по базису имеет вид:

 

, (2.2.8)

 

где – коэффициенты разложения.

 

Введем в рассмотрение величину

 

(2.2.9)

 

Здесь – координаты вектора из целевой функции рассматриваемой задачи (2.2.1); – коэффициенты из (2.2.8).

Если , то

 

(2.2.10)

 

(2.2.11)

 

Теорема 2.2.1 (правило оптимальности).

Если то – решение задачи (2.2.1).

 

Доказательство. Используя (2.2.1), (2.2.3) и (2.2.4), запишем:

 

(2.2.12)

 

Последняя сумма в (2.2.12) не содержит нулевых слагаемых. Рассмотрим произвольную точку , где – допустимое множество задачи (2.2.1), определяемое согласно (2.2.2). Эта точка удовлетворяет уравнению

 

, (2.2.13)

 

правую часть которого преобразуем следующим образом:

 

Сравнивая полученное выражение с (2.2.12) и учитывая, что точку можно разложить по базису единственным образом, приходим к выводу о справедливости равенства

 

(2.2.14)

 

Подчеркнем, что (2.2.14) справедливо Найдем значение целевой функции в точке :

 

(2.2.15)

 

Из условия теоремы, а также из (2.2.9) и (2.2.11) следует:

 

 

Подстановка правой части последнего неравенства в (2.2.15) вместо приводит к неравенству

 

 

В процессе преобразований использовано выражение (2.2.14). Таким образом, . Следовательно, – решение задачи (2.2.1). Теорема доказана.

 

Допустим, что условие теоремы 2.2.1 не выполнено, т.е. . По аналогии с (2.2.8) имеем

 

(2.2.16)

 

Используя (2.2.16), запишем:

, (2.2.17)

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

 

(2.2.18)

 

Используя (2.2.18), преобразуем выражение (2.2.17):

 

(2.2.19)

 

Найдем значение целевой функции в точке :

 

 

(2.2.20)

 

Теорема 2.2.2 (правило отсутствия решения у задачи).

 

Если и если , то задача (2.2.1) не имеет решения.

Доказательство. Рассмотрим вектор , , определенный в соответствии с (2.2.18); , так как , и . Кроме того, согласно (2.2.19), . Таким образом, . Из (2.2.20) следует, что

 

(2.2.21)

 

Если задать последовательность значений в виде , то , т.е. все точки будут принадлежать допустимому множеству (2.2.2) задачи, при этом в соответствии с (2.2.21) значения целевой функции будут стремиться к бесконечности:

 

,

 

т.е. максимум не достигается и, следовательно, задача не имеет решения. Теорема доказана.

Теорема 2.2.3.

 

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

 

Доказательство. Введем величину , которую определим следующим образом:

 

(2.2.22)

 

Отметим, что в силу (2.2.22) и (2.2.4). Подстановка в (2.2.18)

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

Очевидно, что (2.2.19) выполнено. Осталось показать, что . Это следует из (2.2.18) с учетом того, что , а также

 

 

Итак, при переходе к очередной опорной точке ее координаты определяются в соответствии с (2.2.18), где в качестве величины используется значение (2.2.22). В этом случае выражение (2.2.18) можно записать в более подробном виде:

 

(2.2.23)

 

Рассмотрим множество Очевидно, что Покажем, что векторы образуют базис в пространстве . Произвольный вектор может быть представлен в виде разложения по базису :

 

(2.2.24)

 

Согласно (2.2.8), . Отсюда находим:

 

(2.2.25)

 

Подставив это выражение в (2.2.24), получим:

 

, (2.2.26)

 

где .

Итак, в соответствии с (2.2.26), произвольный вектор выражен через . Следовательно, множество векторов образует базис в пространстве и, таким образом, векторы линейно независимы. Отсюда следует, что точка , координаты которой определяются в соответствии с (2.2.23), является опорной, причем . Теорема доказана.

 

После определения новой опорной точки и множества формулы (2.2.8) и (2.2.9) приобретают вид:

 

(2.2.27)

 

Способ вычисления коэффициентов разложения по базису , а также значения устанавливает следующая теорема.

 

Теорема 2.2.4 (связь между параметрами итераций).

 

справедливы соотношения:

 

(2.2.28)

 

(2.2.29)

Доказательство. Используя соотношения (2.2.8) и (2.2.25), выполним следующие преобразования:

 

 

(2.2.30)

 

где

 

Таким образом, справедливость соотношений (2.2.28) доказана, причем их единственность следует из единственности разложения (2.2.30) вектора по базису .

Перейдем к доказательству соотношения (2.2.29). Запишем:

 

 

 

(2.2.31)

 

где в соответствии с (2.2.9). Используя полученный результат (2.2.31), а также формулу (2.2.9), преобразуем второе выражение в (2.2.27):

 

 

Таким образом, подтверждена справедливость формулы (2.2.29). Теорема

доказана.

 

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

Пример 2.2.2

 

 

Здесь

Первую опорную точку найдем с помощью метода, использованного в примере 2.2.1. Набору соответствует линейно независимая совокупность столбцов . В этом случае система (2.2.5) имеет вид:

 

 

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

 

Таблица 2.2.1 Таблица 2.2.1а

 


Дата добавления: 2021-05-28; просмотров: 200;

Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.114 сек.