Линейное программирование

 
 
 
 
 
 
 
 
 
 
 
 
 
 

     рис.2.3.

     Построим  прямые уровня, которые касаются области X. Таких прямых две

 

     Прямая  касается области X в точке О(0, 0), а прямая - в точке    K(2, 2,4). Точка K - пересечением прямых m, n и её координаты находятся как решение системы уравнений

 
 

     Решение системы  значит K(2, 2,4). Точки касания K(2, 2,4) определяют решение задачи линейного программирования. То есть

4. ПОСТАНОВКА  И АЛГОРИТМ РЕШЕНИЯ  СИМПЛЕКСНОГО МЕТОДА.

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

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

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

     1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.

     2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплексную таблицу. Все строки таблицы 1-го шага, за исключением строки Δ_j (индексная строка), заполняем по данным системы ограничений и целевой функции.

     Таблица 3.1.

       
 
 

     Индексная строка для переменных находится  по формуле

 

и по формуле

 

     Возможны  следующие случаи при решении  задачи на максимум:

     — если все оценки Δ_j ≥ 0, то найденное решение оптимальное;

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

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

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

     Если  хотя бы одна оценка Δ_k < 0, то k-й столбец принимаем за ключевой. За ключевую строку принимаем ту, которой соответствует минимальное отношение свободных членов (b_i) к положительным коэффициентам k-гo столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называется ключевым элементом.

     3. Заполняем симплексную таблицу 2-го шага:

     — переписываем ключевую строку, разделив ее на ключевой элемент;

     — заполняем базисные столбцы;

     — остальные коэффициенты таблицы  находим по правилу "прямоугольника". Правило "прямоугольника" заключается в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m + 1)-го столбца h_1,m+1. Тогда элемент i-й строки (m + 2)-го столбца 2-го шага — обозначим его h’_i,m+2 — согласно правилу "прямоугольника" выражается формулой

 

где   — элементы 1-го шага. Оценки можно считать по приведенным выше формулам или по правилу "прямоугольника" Получаем новое опорное решение, которое проверяем на оптимальность, и т.д.

     Примечание. Если целевая функция требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Δ_j при всех j = .

 

5. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ  СИМПЛЕКСНЫМ МЕТОДОМ.

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

 
 
 
 
 

Запишем двойственную задачу

 
 
 
 
 

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

 
 
 
 
 

     Данные, приведённые в канонической задаче, заносим в симплекс таблицу.

     Таблица 3.2.

       
 

     Заполнение  таблицы стандартное, в столбце  “Значения” у оценочной функции ставим 0, т.к. в функции цели постоянное слагаемое 0. Выделяем базисные переменные. Это переменные, для которых столбцы образуют единичную матрицу. Базис образуют . Остальные переменные являются свободными.

     По  заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы. Они представлены в столбце “Значение”. Отметим, что значение функции цели берём с противоположным знаком. Итак,

     В оценочной строке имеются положительные  числа. Значит, решение можно улучшить. Выберем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них, например, первое. Соответствующий столбец называем ведущим. По ведущему столбу и столбцу “Значения” определяем оценку строки. Число из столбца “Значение” делим на соответствующее число из ведущего столбца. Получаем оценку строки. По условию задачи это положительное число. Объявляем ведущей строкой ту, оценка у которой наименьшая. В таблице 3.2 ведущая строка и столбец выделены цветом. На их пересечении находится ведущий элемент. В нашем случае это число 4.

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

     Таблица 3.3.

 

     Из  таблицы 3.3 находим базисные переменные (свободные переменные равны 0) и значение функции. Получаем Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования. Действительно, т.е. получили верное равенство.

     В оценочной строке имеется положительное  число, значит можно перейти к следующей итерации. В таблице 3.3 цветом выделены ведущий столбец и ведущая строка. Суть второй итерации состоит в том, чтобы свободную переменную преобразовать в базисную, а базисную переменную сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 3.4.

     Из  последней таблицы находим базисные переменные и значение функции цели. Получаем Этот результат можно проверить. Действительно, Итак, мы получили верное равенство.

     Таблица 3.4.

 

     В оценочной строке есть одно положительное число. Значит можно перейти к следующей итерации. В таблице 3.4 цветом выделены ведущий столбец и ведущая строка. Суть третьей итерации состоит в том, чтобы свободную переменную преобразовать в базисную, а базисную переменную сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 3.5.

     Таблица 3.5.