Основы симплес метода

 

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Введение 

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

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

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

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

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

     Термин  «программирование» нужно понимать в смысле «планирования». Он был  предложен в середине 1940-х годов  Джорджем Данцигом, одним из основателей  линейного программирования, ещё  до того, как компьютеры были использованы для решения линейных задач оптимизации.

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

     

2. Основы  симплекс-метода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 Таблица  1 
 
 
 

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

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

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

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

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

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

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

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

Таблица 1.1

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

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

Таблица 1.2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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