Лекция 7. Геометрическое решение задач линейного программирования. Основные теоремы линейного программирования. Симплекс метод для решения задач линейного программирования.

Транспортная задача.

Задача о смесях (планирование состава продукции).

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

На птицеферме употребляются два вида кормов - I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II - 2 рубля.

Составьте ежедневный рацион кормления птицы так, чтобы обеспечить наиболее дешевый рацион.

Представим условие задачи в таблице .

Cформулируем задачу линейного программирования.

Обозначим: x₁ - количество корма I в дневном рационе птицы, x₂ - количество корма II в дневном рационе птицы.

Формулировка ЗЛП:

= 3x1 + 2x2 → min;
x1 + 4x2 ≥ 1, x1 + 2x2 ≥ 4, x1 ≥ 1;
x1 ≥ 0, x2 ≥ 0.

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

Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

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

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

Сформулируем ЗЛП:

= 7x11 + 6x12 + 4x13 + 3x21 + 8x22 + 5x23 + 2x31 + 3x32 + 7x33 → min;
x11 + x12 + x13 = 120, x21 + x22 + x23 = 100, x31 + x32 + x33 = 80, x11 + x21 + x31 = 90, x12 + x22 + x32 = 90, x13 + x23 + x33 = 120;
xij ≥ 0, (, ).

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

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

Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.

1. Сформулировать ЗЛП.

2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

3. Найти полуплоскости, определяемые каждым из ограничений задачи.

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

5. Построить прямую c₁x₁ + c₂x₂ = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке.

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

1. Выше уже приводилась формулировка задачи, здесь нам остается лишь повторить ее:

= 2x1 + 4x2 → max;
4x1 +6x2 ≤ 120, 2x1 +6x2 ≤ 72, x2 ≤ 10;
x1 ≥ 0, x2 ≥ 0.

2. Теперь построим прямые, соответствующие каждому из функциональных ограничений задачи. Эти прямые обозначены на рисунке (1), (2) и (3).

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

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

5. Прямая, соответствующая целевой функции, на рисунке представлена пунктирной линией.

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

7. Осталось вычислить координаты точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем: , . Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке .

Таким образом, для максимизации прибыли компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.

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

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

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

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

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

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

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

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

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

Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

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

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

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

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

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

Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений).

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

= c1x1 + c2x2 + ... + cnxn ->max;

a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≤ b2, ... am1x1 + am2x2 + ... + amnxn ≤ bm;

xj ≥ 0,

Еще раз повторим формулировку задачи из нашего примера.

= 2x1 + 4x2 → max;
4x1 +6x2 ≤ 120, 2x1 +6x2 ≤ 72, x2 ≤ 10;
x1 ≥ 0, x2 ≥ 0.

Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений).

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

a11x1 + a12x2 + ... + a1nxn + y1 = b1, a21x1 + a22x2 + ... + a2nxn + y2 = b2, ... am1x1 + am2x2 + ... + amnxn + ym = bm.

Обозначим добавочные переменные несколько иначе, а именно: y₁ = x_n+1, y₂ = x_n+2, ..., y_m = x_n+m, где n - число переменных в исходной задаче, m - число уравнений.

Все дополнительные переменные также должны быть неотрицательными.

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

Выполним второй шаг для нашего примера.

4x1 +6x2 + x3 = 120, 2x1 +6x2 + x4 = 72, x2 + x5 = 10.

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

При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные x_n+1, x_n+2, ..., x_n+m. Ниже приведены исходная симплексная таблица в общем виде и в применении к рассматриваемой нами задаче.

Таблица 1. Общий вид исходной симплекс-таблицы

Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂, ..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 2. Исходная симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 120, x₄ = 72, x₅ = 10. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 4. Проверка условия: все c_j ≤ 0. Если НЕТ - осуществляется переход к шагу 5, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

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

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

Шаг 6. Проверка условия: все a_ir ≤ 0. Если ДА - целевая функция неограничена и решения нет, если НЕТ - переход к шагу 7.

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

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

Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для air > 0,

где s - номер разрешающей строки.

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

Проиллюстрируем выполнение шага 7, обратившись к нашему примеру.

Для первой строки: D1 = 120 / 6 = 20.

Для второй строки: D2 = 72 / 6 = 12.

Для третьей строки: D3 = 10 / 1 = 10.

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

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

Исходная симплекс-таблица нашего примера с выделенными цветом разрешающей строкой и разрешающим столбцом представлена ниже (таблица 3).

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

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

Для элементов разрешающей строки используются следующие формулы:

где s - номер разрешающей строки,

r - номер разрешающего столбца,

, - новые значения пересчитываемых элементов,

as_j, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

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

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

.

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

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

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

, т.е.

Аналогичным образом пересчитываются остальные элементы.

По окончании пересчета осуществляется возврат к шагу 4.

Полностью результат пересчета для нашего примера можно видеть в таблице 3.

Таблица 3. Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (второе базисное решение)

Таким образом, в новом базисном решении базисными переменными являются: x₂ = 10, x₃ = 60, x₅ = 12 (соответствующие значения можно видеть в последнем столбце таблицы). Неосновные переменные x₁ и x₅ равны нулю. Значение целевой функции в этом случае равно 40 (значение можно видеть в правой нижней ячейке таблицы).

Доведем решение нашего примера до конца.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₁, поскольку здесь содержится единственный положительный элемент нижней строки. Стало быть, переменную x₁ будем переводить в основные.

Далее. Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и вторую строки, поскольку для третьей строки в разрешающем столбце находится нуль. Найдем частное от деления элемента b_i на элемент, находящийся в разрешающем столбце:

Для первой строки: D1 = 60 / 4 = 15.

Для второй строки: D2 = 12 / 2 = 6.

Наименьший результат деления - во второй строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. переводить в неосновные (исключать из базиса) будем переменную x₄.

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 4). Таблица 4. Симплекс-таблица (второе базисное решение) с выделенными разрешающей строкой и столбцом

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

Таблица 5. - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (третье базисное решение)

Таким образом, в очередном (третьем) базисном решении основными переменными являются: x₁ = 6, x₂ = 10, x₃ = 36. Неосновные переменные x₄ и x₅ равны нулю. Значение целевой функции для этого решения равно 52.

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

Шаг 5. Выберем разрешающий столбец. Им окажется столбец x₅, поскольку здесь содержится единственный положительный элемент нижней строки. Переменную x₅ будем переводить в основные.

Шаг 6. Проверка показывает, что в разрешающем столбце есть положительные элементы, следовательно, можно продолжать решение.

Шаг 7. Определим разрешающую строку. При этом будем рассматривать лишь первую и третью строки, поскольку для второй строки в разрешающем столбце находится отрицательное число. Найдем частное от деления элемента bi на элемент, находящийся в разрешающем столбце:

Для первой строки: D1 = 36 / 6 = 6.

Для третьей строки: D2 = 10 / 1 = 10.

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

Ниже приведена симплекс-таблица с выделенными разрешающей строкой и столбцом (таблица 6).

Таблица 6. Симплекс-таблица (третье базисное решение) с выделенными разрешающей строкой и столбцом

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

Таблица 7. - Симплекс-таблица для задачи о хоккейных клюшках и шахматных наборах (четвертое базисное решение)

Таким образом, в очередном (четвертом) базисном решении основными переменными являются: x₁ = 24, x₂ = 4, x₅ = 6. Неосновные переменные x₃ и x₄ равны нулю. Значение целевой функции для этого решения равно 64.

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

, , .

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