Модифицированный симплекс метод

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ  РФ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

ИВАНОВСКАЯ  ГОСУДАРСТВЕННАЯ  ТЕКСТИЛЬНАЯ АКАДЕМИЯ

(ИГТА) 
 

Курсовая  работа

по математическому  программированию

на тему:

 «Модифицированный симплекс – метод». 
 
 
 

                                      Выполнила:        студентка группы 2т9

                                                                   Нохрина Ксения

                                      Специальность: статистика

                                      Номер зачетной книжки: 071194

                                      Проверила: Лысова М. А. 

                                                                                                             

Иваново - 2009 

Оглавление

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение 

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

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

     Симплекс-метод.

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

     Одними  из первых, исследовавшими в общей  форме задачи линейного программирования, были: Джон фон Нейман, советский  академик Л. В. Канторович. Джеймс Данциг (1947 г.) - разработал симплекс метод.

     Наиболее  известным и широко применяемым  на практике для решения общей  задачи линейного программирования (ЛП) является симплекс-метод. Несмотря на то, что симплекс-метод является достаточно эффективным алгоритмом, показавшим хорошие результаты при решении прикладных задач ЛП, он является алгоритмом с экспоненциальной сложностью. Причина этого состоит в комбинаторном характере симплекс-метода, последовательно перебирающего вершины многогранника допустимых решений при поиске оптимального решения. Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.

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

     Модифицированный  симплекс-метод.

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

     ∆_j=Z_j-c_j

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

     Ω=С_б*В^-1,

     Где В^-1 – матрица, обратная матрице В, составленной из компонент векторов данного базиса, а затем находят числа ∆_j по формуле

     ∆_j=ΩР_j-c_j

  Определим компоненты вектора Ω и чисел  ∆_j в случае решения основной задачи линейного программирования модифицированным симплекс-методом.

     Итак, пусть дана задача линейного программирования, записанная в форме основной задачи, и пусть для нее найден опорный  план, который определяется базисом, образованным векторами Р_i1, Р_i2,…, Р_im.

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

  Вспомогательная таблица  отличается от обычной симплекс-таблицы тем, что в ней содержатся дополнительные столбцы и строки, в которых соответственно записывают координаты векторов Ω⁽ⁱ⁾ и значения ∆j, получаемые в процессе нахождения решения задачи.

  Основная  таблица отличается от обычной симплекс-таблицы, во-первых, тем, что вместо столбцов векторов P_j с соответствующими числами с_j записывают столбцы векторов A_i, координатами которых являются соответствующие столбцы матрицы В^-1; во-вторых, в (m + 1)-й строке записывают компоненты векторов Ω, а не числа ∆_j, в-третьих, основная таблица имеет один дополнительный столбец, в первых т строках которого записывают координаты вектора P_s в базисе Р_i1, Р_i2,…, Р_im и который было бы целесообразно включить в базис на следующей итерации.

     Чтобы определить вектор P_s, сначала находят вектор Ω^(l). Его компоненты определяют как скалярное произведение вектора С_б на соответствующие векторы А_i, т.е. по формуле Ω=С_б*В^-1. Найденные компоненты вектора Ω^(l) записывают в последней строке основной таблице и в столбце Ω^(l) вспомогательной таблицы. После этого по формуле ∆_j=ΩР_j-c_j находят элементы (m+1)-й строки вспомогательной таблицы. Если среди найденных чисел (m+1)-й строки вспомогательной таблицы нет отрицательных, то исходный опорный план является оптимальным. Если же таковые есть, то либо задача не имеет решения, либо можно перейти к новому опорному плану, при котором значение целевой функции не уменьшится. Для выяснения этого выбирают среди отрицательных чисел (m+1)-й строки вспомогательной таблицы наибольшее по абсолютной величине. В том случае, когда таких чисел несколько, берут какое-нибудь одно. Пусть этим числом является ∆_s ⁽¹⁾. Тогда последний столбец основной таблицы отводят для вектора P_s. В первых т строках этого столбца записывают компоненты вектора P_s в базисе Р_i1, Р_i2,…, Р_im. Они получаются в результате умножения матрицы В^-1, записанной в основной таблице, на вектор Р_s, компоненты которого указаны во вспомогательной. После определения чисел: x_i1S , x_i2S,…, x_imS выясняют, имеются ли среди них положительные или нет. Если таких чисел нет, то задача не имеет решения. Если же положительные числа имеются, то переходят к новому опорному   плану   задачи.   Для   этого   находят   Пусть min (х_iko/х_iks) = x_iro/х_irS. Тогда новый опорный план определяется базисом, получаемым из исходного исключением из него вектора P_ir, и введением вместо него вектора P_s. Считая элемент X_irs разрешающим, а r- ю строку и столбец вектора P_s направляющими, переходят к новой основной таблице. Первые m строк столбцов векторов Р_о, А₁, А₂,… А_m новой таблицы находят по известным правилам перехода от одной симплекс-таблицы к другой, рассмотренным выше. После того, как эти элементы определены, находят вектор Ω⁽²⁾. Компоненты этого вектора записывают как в новой основной таблице, так и во вспомогательной таблице . Затем вычисляют числа ∆_j⁽²⁾и проверяют новый опорный план на оптимальность. Если план не оптимален, то либо устанавливают неразрешимость исходной задачи, либо переходят к новому опорному плану. Продолжая итерационный процесс, после конечного числа шагов либо находят оптимальный план задачи, либо устанавливают ее неразрешимость.

  Таким образом, процесс нахождения решения  задачи модифицированным симплекс-методом включает следующие этапы:

1. Находят опорный план задачи.

  2. Вычисляют матрицу В^-1, обратную матрице В, составлен- 
ной из компонентов векторов исходного базиса.

3. Находят вектор Ω=С_б*В^-1.

    4. Вычисляют числа ∆_j=ΩР_j-c_j. Если все ∆_j не отрицательны, то исследуемый опорный план является оптимальным. Если 
же среди чисел ∆_j имеются отрицательные, то выбирают среди 
них наибольшее по абсолютной величине.

5. Вычисляют компоненты вектора P_s в исходном базисе. Если среди компонент вектора Р_s нет положительных, то целевая функция задачи не ограничена на множестве планов. Если же среди компонент вектора P_s имеются положительные, то переходят к новому опорному плану.
6. По известным правилам симплекс-метода находят разрешающую строку и вычисляют положительные компоненты нового опорного плана, а также матрицу В^-1 , обратную матрице В, составленной из компонент векторов нового базиса.
7. Проверяют новый опорный план на оптимальность и в случае необходимости проводят вычисление, начиная с этапа 3.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Решение ЗЛП модифицированным симплекс-методом.

     Решить  задачу линейного программирования, используя модифицированный симплекс- метод, состоящую в определении  минимального значения функции F(x)=3x₁+2х₂+4х₃+5х₄+3х₅+2х₆ при условиях: 

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

Найти  минимум функции:

F(x)=3x₁+2х₂+4х₃+5х₄+3х₅+2х₆ + 0х₇+0х₈+0х₉-Мх₁₀ – Мх₁₁ – Мх₁₂ 

     Расширенная задача имеет опорный план:

Х = (0,0,0,0,0,0,0,0,0,12,18,32),  который определяется базисом, образованным векторами Р₁₀, Р₁₁, Р₁₂. Составляем вспомогательную и основную таблицы (1 и 2). Сначала в таблицу 1 на основе исходных данных заполняем первые три строки столбцов Р₀, Р₁,…, Р₁₂, а в таблице 2 – первые три строки столбцов Р₀, А₁, А₂, А₃.