Лекция №1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Лекция № 2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача с двумя переменными

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

Задача линейного программирования с двумя переменными должна иметь систему ограничений, представляющую собой систему неравенств. Неравенства могут быть как вида " £ ", так и " ³ ". Условия неотрицательности могут отсутствовать. Математическая модель должна иметь вид

(2.1)

(2.2)

.

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

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

Доказательство. В системе координат О построим прямую (L) и ее нормаль (рис. 2.1).

Рис. 2.1

Прямая (L) разбивает плоскость О на две полуплоскости: верхнюю ( ), соответствующую направлению нормали , и нижнюю ( ). Пусть произвольно выбранная точка М( ) принадлежит ( ), ее проекцией на прямую (L) является точка . Вектор . Координаты векторов и совпадают с координатами точек М и А, т. е. = ( ), . Вектор коллинеарен вектору , поэтому = ×l, где l некоторое число. Найдем скалярное произведение . Запишем это равенство через координаты векторов . Так как точка А принадлежит прямой (L), то , получаем .

Отсюда следует, что если l>0, т. е. M Î( ), то и тогда . Если же l<0, M Î( ), то и .

Пример 2.1. Найти область решений неравенства .

Решение. Строим прямую (рис. 2.2).

Рис. 2.2

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

В рассматриваемом примере в качестве "пробной" точки возьмем О(0, 0). Подставляем координаты этой точки в неравенство, получаем 2 × 0 + 3 × 0 £ 6 Û 0 £ 6, следовательно, областью решений является полуплоскость, содержащая начало координат. Этот факт отмечаем на рисунке стрелками.

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

Линией уровня называется прямая, в точках которой целевая функция постоянна Z(X) = . Уравнение линий уровня

, с = const.

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

Рис. 2.3

Доказательство. Пусть целевая функция задачи линейного программирования имеет вид Z(X) = . В системе координат О построим две линии уровня (L ) и (L ) (рис. 2.3). Их общая нормаль . Пусть точка М( ) Î (L ), а точка Î(L ) является проекцией М на (L ). Вектор , = ( ), . Так как коллинеарен вектору , то вектор = ×l, где l число. Скалярное произведение . Используя координаты векторов и , можно записать . Так как , , то .

Отсюда получаем следующие выводы: 1) если линия уровня перемещается в направлении нормали из положения (L ) к (L ), то l > 0 и, следовательно, ; 2) если же линия уровня перемещается в направлении противоположном направлению нормали из положения (L ) к (L ), то l < 0 и, следовательно, .

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

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

Алгоритм графического метода решения задач линейного программирования с двумя переменными заключается в следующем.

1. Строится область допустимых решений.

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

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

4. Линия уровня перемещается до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум – в противоположном.

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

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

Пример 2.2. Решить задачу линейного программирования

Рис. 2.4

Решение. Изобразим на плоскости систему координат (рис. 2.4) и построим граничные прямые области допустимых решений.

Прямые, ограничивающие ОДР:

Область допустимых решений определяется многоугольником ОАВСD. Для линий уровня (с = const) строим нормальный вектор . Перпендикулярно вектору построим одну из линий уровня (на рисунке она проходит через начало координат). Так как задача на максимум, то перемещаем ее в направлении вектора до опорной прямой. На рисунке видно, что опорная прямая проходит через точку B, являющуюся точкой пересечения первой и второй граничных прямых, . Для определения координат точки В решаем систему уравнений

Получаем = 3, = 6. Данному оптимальному решению
X = (3; 6) соответствует максимальное значение целевой функции
max Z(X) = 2 × 3 + 4 × 6 =30.

Ответ: max Z(X) = 30 при X = (3; 6).

Пример 2.3 Решить задачу линейного программирования.

Рис. 2.5

Решение. Строим область допустимых решений, нормаль линий уровня и одну из линий уровня, имеющую общие точки с этой областью (рис. 2.5). Перемещаем линию уровня в направлении противоположном направлению нормали , так как решается задача на отыскание минимума функции. Нормаль линии уровня и нормаль = (2; 1) второй граничной прямой, в направлении которой перемещаются линии уровня, параллельны, так как их координаты пропорциональны 4/2 = 2/1. Следовательно, опорная прямая совпадает со второй граничной прямой области допустимых решений, проходит через две угловые точки этой области и . Задача имеет бесконечное множество оптимальных решений, являющихся точками отрезка . Находим точки , , решая соответствующие системы уравнений.

Вычисляем

Ответ: при

Пример 2.4. Решить задачу линейного программирования.

Рис. 2.6

Прямые, ограничивающие ОДР:

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

Ответ: .

Пример 2.5. Решить задачу линейного программирования.

Рис. 2.7

Решение. Строим прямые линии, соответствующие неравенствам системы ограничений и находим полуплоскости, являющиеся областями решений этих неравенств (рис. 2.7). Область допустимых решений задачи – пустое множество. Задача не имеет решения ввиду несовместности системы ограничений.

Ответ: система ограничений несовместна.

Лекция №3 ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Графический метод решения задач линейного
программирования с n переменными

Данным методом решаются задачи линейного программирования, имеющие каноническую форму и удовлетворяющие условию , где n – число неизвестных системы, r – ранг системы векторов-условий (число линейно независимых уравнений системы). Если уравнения системы ограничений линейно независимые, то r = m.

Рассмотрим алгоритм метода на конкретном примере.

Пример 2.6. Решить графическим методом.

,

.

Решение.

1. Проверяем условие применимости графического метода. Нетрудно видеть, что любые два из векторов-столбцов системы ограничений, например, , являются линейно независимыми, так как их координаты непропорциональны, поэтому ранг системы векторов-условий r = 2. Находим n - r = 4 - 2 =2 £ 2. Следовательно, метод применим.

2. Приведем систему ограничений-уравнений к равносильной, разрешенной с помощью метода Жордана – Гаусса. Одновременно исключим разрешенные неизвестные из целевой функции. Для этого

Т а б л и ц а 2.1

				b
				–5
		–1
				–5

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

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

которая решается графическим методом (рис. 2.8).

Рис. 2.8

Оптимальное решение ; = (2; 0). Значение целевой функции = 4 × 2 + 0 + 5 = 13.

4. Используем систему ограничений исходной задачи, приведенную к каноническому виду,

и оптимальное решение задачи с двумя переменными = (2; 0) для нахождения оптимального решения исходной задачи

;

.

Записываем оптимальное решение исходной задачи
= (3; 0; 2; 0). Значение целевой функции на оптимальном решении совпадает со значением целевой функции для вспомогательной задачи = 1 × 3 + 2 × 0 + 5 × 2 + 3 × 0 = 13.

Ответ: max Z(X) = 13 при = (3; 0; 2; 0).

Задания для самостоятельного решения

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

Пример 2.7. ,

Пример 2.8. ,

Пример 2.9. ,

Пример 2.10. ,

Пример 2.11. ,

Пример 2.12. ,

Лекция№4. СВОЙСТВА РЕШЕНИЙ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

Лекция№5-6.

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

Это метод целенаправленного перебора опорных решений задачи линейного программирования, поэтому его часто называют методом улучшения опорных решений.

Симплексный метод позволяет выполнить следующее:

1) найти начальное опорное решение;

2) перейти к новому опорному решению, на котором значение целевой функции будет ближе к оптимальному решению, т. е. улучшить опорное решение;

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

Название метод получил от вида области допустимых решений задачи, для которой он первоначально применялся. Область допустимых решений этой задачи имела простейший (simple) вид (рис. 3.6).

Рис. 3.6

5.1. Нахождение начального опорного решения и переход
к новому опорному решению

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

(4.1)

(4.2)

(4.3)

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

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

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

Пусть разрешающим элементом для преобразования Жордана является коэффициент при неизвестной в уравнении с номером l. В результате преобразования Жордана правые части уравнений, как известно, пересчитываются по следующим формулам:

.

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

.

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

.

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

.

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

а) если , то ввиду того, что , , , без дополнительных условий имеем ;

б) если же , то неравенство

поделим на , получим

.

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

. (4.4)

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

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

Используя данное условие, можно найти начальное опорное решение.

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

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

.

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

Очевидно, для перехода от этого опорного решения к новому необходимо использовать соотношение

при , (4.5)

где k – номер вектора, вводимого в базис, l – номер вектора, выводимого из базиса, – координаты опорного решения, – коэффициенты разложения вектора по базису опорного решения.

Пример 5.1. Найти начальное опорное решение и путем перебора опорных решений найти оптимальное решение задачи

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

Т а б л и ц а 5.1

,

.

,

.

, .

,

.

Сравниваем значения целевой функции на полученных опорных решениях, min{-20, 4, -28} = -28. Находим оптимальное опорное решение

.

Ответ: при .

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

5.2. Преобразование целевой функции при переходе
от одного опорного решения к другому

Пусть имеется опорное решение задачи линейного программирования (4.1)-(4.3) c базисом . Значение целевой функции задачи на этом этапе решения равно . Используя преобразование Жордана с разрешающим элементом , перейдем к другому опорному решению с базисом , т. е. введем в базис вектор и исключим . Значение целевой функции на этом этапе решения равно

.

Формулы пересчета правых частей уравнений системы при преобразовании Жордана имеют вид

; ; i = 1, 2, …, m; i ¹ l.

Используя эти формулы, получим

,

т. е. . (4.6)

Отсюда находим приращение целевой функции при переходе от одного опорного решения к другому

. (4.7)

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

(4.8)

или в векторной записи

, (4.9)

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

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

.

Решение. Задача имеет начальное опорное решение с базисом . Для удобства расчета запишем исходные данные в следующую таблицу, называемую симплексной (табл. 4.2).

Т а б л и ц а 4.2

				-4
Б Сб
			-1	-4
			-2
			-13

;

;

.

Оценки для векторов, входящих в базис, всегда равны нулю.

Улучшение опорного решения

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

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

Перейдем к новому опорному решению , введем в базис вектор и исключим из базиса вектор . В этом случае приращение целевой функции равно

.

Решение невырожденное, поэтому параметр , вычисляемый по формуле (4.5), отличен от нуля ( > 0). Так как > 0, , то

.

Следовательно, значение целевой функции на новом опорном решении будет больше, чем на первом .

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

Следствие 1 (условие наибольшего приближения к оптимальному решению). Для наибольшего изменения целевой функции при улучшении опорного решения необходимо выбор вектора, выводимого из базиса (с номером l) и вводимого в базис (с номером k), производить из условий:

– в задаче на максимум ; (4.10)

– в задаче на минимум . (4.11)

В упрощенном варианте выбор вектора, вводимого в базис, можно производить с использованием условий:

– в задаче на максимум ; (4.12)

– в задаче на минимум . (4.13)

Этот вариант перехода к новому опорному решению обычно используется при расчетах на ЭВМ.

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

– в задаче на максимум ; (4.14)

– в задаче на минимум . (4.15)

Действительно, если Z(x) , , , то

,

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

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

. (4.16)

Здесь предполагается, что в базис оптимального решения входят первые m векторов.

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

$ k Î {m+1, m+2, ..., n}: . (4.17)

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

– в задаче на максимум и ; (4.18)

– в задаче на минимум