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

состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и неотрицательности. Геометрический метод решения ЗЛП Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации. 1. Сформулировать ЗЛП. 2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств. 3. Найти полуплоскости, определяемые каждым из ограничений задачи. 4. Найти область допустимых решений. 5. Построить прямую c1x1 + c2x2 = h, где h – любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений. 6. Перемещать найденную прямую параллельно самой себе в направлении увеличения (при поиске максимума) или уменьшения (при поиске минимума) целевой функции. В результате, либо отыщется точка, в которой целевая функция принимает максимальное (минимальное) значение, либо будет установлена неограниченность функции на множестве решений. 7. Определить координаты точки максимума (минимума) функции и вычислить значение функции в этой точке. Симплекс-метод решения ЗЛП Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования. В основу симплексного метода положена идея последовательного улучшения получаемого решения. Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение – вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум). Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным. Процесс применения симплексного метода предполагает реализацию трех его основных элементов: способ определения какого-либо первоначального допустимого базисного решения задачи; правило перехода к лучшему (точнее, не худшему) решению; критерий проверки оптимальности найденного решения. Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную. Далее рассмотрим симплексный алгоритм, не углубляясь в его обоснование. Реализация симплекс-алгоритма включает восемь шагов. Шаг 1. Формулировка ЗЛП (формирование целевой функции и системы ограничений). Для определенности будем считать, что решается задача на отыскание максимума. Ниже приведем общую постановку такой задачи.  = c1x1 + c2x2 + … + cnxn max; a11x1 + a12x2 + … + a1nxn ≤ b1,a21x1 + a22x2 + … + a2nxn ≤ b2, …             am1x1 + am2x2 + … + amnxn ≤ bm; xj ≥ 0,    Шаг 2. Приведение задачи к канонической форме (перевод функциональных ограничений в систему уравнений). Для реализации шага в ограничения задачи вводятся дополнительные переменные. Ниже приведен порядок выполнения этой операции. a11x1 + a12x2 + … + a1nxn + y1 = b1,a21x1 + a22x2 + … + a2nxn + y2 = b2, …             am1x1 + am2x2 + … + amnxn + ym = bm. Обозначим добавочные переменные несколько иначе, а именно: y1 = xn+1, y2 = xn+2, …, ym = xn+m, где n – число переменных в исходной задаче, m – число уравнений. Все дополнительные переменные также должны быть неотрицательными. В отношении добавочных переменных нужно сделать еще одно важное замечание. Все они должны иметь тот же знак, что и свободные члены системы ограничений. В противном случае используется так называемый M-метод (метод искусственного базиса). Шаг 3. Построение исходной симплекс-таблицы (получение первоначального допустимого базисного решения). При ручной реализации симплексного метода удобно использовать так называемые симплексные таблицы. Исходная симплекс-таблица соответствует первоначальному допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные xn+1, xn+2, …, xn+m. Ниже приведены исходная симплексная таблица в общем виде (таблица 2.4) Таблица 2.4 – Общий вид исходной симплекс-таблицы базис переменные bi x1 x2 … xn xn+1 … xn+m xn+1 a11 a12 … a1n 1 0 0 b1 xn+2 a21 a22 … a2n 0 … 0 b2 … … … … … … … … … xn+m am1 am2 … amn 0 0 1 bm cj c1 c2 … cn 0 0 0 L Итак, в левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b1, b2, …, bm. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении (). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты aij при переменных системы ограничений. Шаг 4. Проверка условия: все cj ≤ 0. Если НЕТ – осуществляется переход к шагу 5, если ДА – задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение. Шаг 5. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием: где r – номер разрешающего столбца. Таким образом, при определении разрешающего столбца просматривается последняя строка симплексной таблицы и в ней отыскивается наибольший положительный элемент. Шаг 6. Проверка условия: все air ≤ 0. Если ДА – целевая функция неограничена и решения нет, если НЕТ – переход к шагу 7. Таким образом, необходимо проверить элементы разрешающего столбца. Если среди них нет положительных, то задача неразрешима. Шаг 7. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:    для air > 0, где s – номер разрешающей строки. Таким образом, для тех строк, где элементы разрешающего столбца положительны, необходимо найти частное от деления элемента bi (последний столбец таблицы) на элемент, находящийся в разрешающем столбце. В качестве разрешающей выбирается строка, для которой результат такого деления будет наименьшим. Шаг 8. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается. Для элементов разрешающей строки используются следующие формулы:     где s – номер разрешающей строки, r – номер разрешающего столбца,  ,  – новые значения пересчитываемых элементов, asj, bs – старые значения пересчитываемых элементов, asr – старое значение разрешающего элемента. Таким образом, при пересчете элементов разрешающей строки каждый ее элемент делится на разрешающий элемент. Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:    . Элементы, не принадлежащие разрешающим столбцу и строке, пересчитываются по так называемому правилу прямоугольника: мысленно выделяется прямоугольник, в котором элемент, подлежащий пересчету и разрешающий элемент образуют одну из диагоналей. Формулы будут иметь следующий вид:           где  ,  ,  ,  – новые значения пересчитываемых элементов, aij, bi, cj, L – старые значения пересчитываемых элементов. По окончании пересчета осуществляется возврат к шагу 4. Двойственная задача – геометрический метод решения Каждой задаче линейного программирования может быть поставлена в соответствие другая вполне определенная задача линейного программирования, такая, что при решении одной из них одновременно решается и другая. Эти задачи были названы парой взаимодвойственных задач. Исходная задача Двойственная задача ; ; Правила построения двойственной пары Целевая функция исходной задачи задается на максимум, а целевая функция двойственной – на минимум. Коэффициенты при переменных в системах ограничений описываются матрицами, которые являются транспонированными относительно друг друга. Число переменных в двойственной задаче равно числу соотношений в системе ограничений исходной задачи. Число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи и наоборот. Если на j переменную исходной задачи наложено уcловие неотрицательности , то j-тое ограничение двойственной задачи является неравенством. Если может принимать как положительные, так и отрицательные значения, то j-тое соотношение в системе ограничений двойственной задачи – уравнение. Аналогично связаны ограничения исходной задачи и переменные двойственной. Если i-тое соотношение в системе исходной задачи является неравенством, то i-тая переменная двойственной задачи . В противном случае может принимать как положительные, так и отрицательные значения. При решении двойственных задач возможны три случая: обе задачи разрешимы; области допустимых решений обеих задач пусты; одна задача имеет неограниченную область допустимых решений, вторая – пустую. Двойственная задача – симплекс-метод Двойственный симплекс-метод позволяет за конечное число итераций найти оптимальный план двойственно невырожденной задачи, или обнаружить, что множество планов пусто.  Решение системы линейных уравнений, определяемое базисом, называется псевдопланом задачи, если  для любого j. Двойственный симплекс-метод позволяет за конечное число итераций найти оптимальный план двойственно невырожденной задачи, или обнаружить, что множество планов пусто. Алгоритм двойственного симплекс-метода Этап 1 Находим псевдоплан задачи. Этап 2 Проверяем псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено

Часть выполненной работы