Инфоурок Другое СтатьиСтатья на тему " О математических методах исследования в задачах Линейного программирования " .

Статья на тему " О математических методах исследования в задачах Линейного программирования " .

Скачать материал

 

О математических методах исследования в задачах

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

 

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

 

Найти   f0(x)=c1x1+c2x2+...+cnxn                       (1)

 

 

где  x=(x1,x2,...,xn)-вектор переменной

        cj, j=1,2,...,n- коэффициенты целевой функции

        aij, i=1,2,...,n; j=1,2,...,n- коэффициент ограничений

        b=(b1,b2,...,bn)-вектор свободных членов

        A=[aij]m´n      

 

ЗЛП в стандартной форме записи:

 

[f0(x)=]                          [g0(y)=]

R=                             Q=

Где: АТ-транспонированная матрица AТ=[aij]m´n      

 

ЗЛП в канонической форме записи:

 

[f0(x)=]                          [g0(y)=]

R=                             Q=

 

Эквивалентные преобразования ЗЛП.

 

  Эквивалентные преобразования не изменяют решения ЗЛП , то есть эквивалентность относительно решения.

 

1.     Переход от задачи  max к задаче min:

[f0(x)=]-от этой задачи перейти к задаче на min

f0(x)= -[f0(x)]

 

f0(x)==[-]

 

g0(y)== -g0(y)=[]

 

2.Переход от ограничения равенства к ограничению неравенства (заключается в переходе к двум противоположным неравенствам).

 

³bi

£bi

При решении задачи  на  f0(x) имеем следующие ограничения:

 

-£bi

£bi

При решении задачи на f0(x) ограничения следующие:

³bi

-³bi

 

3.     Переход от ограничений неравенств к ограничениям равенства:

£bi  добавляется неотрицателбная часть: +xn+i=bi, где xn+i³0 (дополнительная переменная)

³cj        вычтем константу :  -xm+j=cj ,где xм+j³0

 

4.     Переход от переменной неопределённого знака к неотрицательной переменной.

      x   ³£ 0   

Введём две новые переменные:Uj³ 0;

                                                      Vj³0.

Получим: xjUj -Vj

5. Переход от переменной, ограниченной сверху к неотрицательной переменной:

xk³dk, dk=const,dk>0

Введём новые переменные: Wk=xk-dk , Wk>0

 

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

 

Симплекс – метод решения задачи линейного программирования на максимум в стандартной форме записи при .

 

 

 

          Симплекс – метод для решения задачи линейного программирования на максимум основан на методе Жордана (1838-1922) решения систем линейных алгебраических уравнений.

          Американский математик Дж. Данциг в 1949 году введением строки для целевой функции применил этот метод для решения задачи линейного программирования.

          Основоположником же рассматриваемого метода считается Канторович, представивший в 1938 году “метод допустимого улучшения плана”, предполагая, что начальное решение уже имеется, в отличие от Данцига, у которого начальное решение находится с помощью симплекс – преобразований. Однако Нобелевская премия была получена им лишь в 1975 году.

 

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

 

          Рассмотрим симплекс – метод решения задачи линейного программирования на максимум в стандартной форме записи на следующем примере:

 

.

От задачи (1) – (3) перейдем к задаче в канонической форме записи. Для этого введем дополнительные переменные  и разрешим относительно них систему ограничений – равенств, при этом :

 

 

 

 

 

 

 

.

         

Введем вектор , т. е.

Тогда

        Заметим, что симплекс – метод применяется только при выполнении ограничения (3).

 

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

1.    

2.     - начало итерационного процесса

3.    

4.      иначе см. пункт 12 (столбец  будет разрешающим)

5.      иначе см. пункт 14

6.    

7.    

8.    

9.    

10. - переход к следующей итерации.

11. - новый базис. Далее переходим на пункт 3.

Особенности алгоритма.

 

 

 

12. Если , то существует альтернативный оптимум, и см. пункт 5

13. , то найдено оптимальное решение, иначе см. пункт 14.

14. Задача линейного программирования не имеет смысла.

15. Конец

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕМА О СИМПЛЕКСНЫХ ПРЕОБРАЗОВАНИЯХ

 

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

Доказательство:

          Рассмотрим разрешающую строку :

 (1)

Тогда

          Покажем, что это решение не улучшает целевой функции:

Введем обозначение: , причем .(2)

Тогда .

          Теорема доказана.

 

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

Алгебраический смысл итерационного процесса симплекс – метода заключается в введении в базисные переменные , которая увеличивает целевую функцию, и

 

 

выводе переменной , что не нарушает условие неотрицательности базисных переменных:

.

 

Примечание 2. Рассмотренная задача линейного программирования всегда имеет решение, по крайней мере тривиальное, т. е.

. Для симплекс – таблицы .

 

Примечание 3. Если среди свободных членов задачи линейного программирования имеются отрицательные, то симплекс – метод разбивается на два этапа:

·        Нахождение дополнительного решения

·        Нахождение оптимального решения

 

НАХОЖДЕНИЕ ДОПУСТИМОГО РЕШЕНИЯ

1.    

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

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

 

Решение задачи линейного программирования на минимум  симплекс-методом

 

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

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

Пусть дана задача

 

 

 

 

 

 

Нахождение оптимального решения состоит из двух этапов:

1.     Нахождение дополнительного решения.

2.     Нахождение оптимального решения.

1.    

     , иначе задача не имеет смысла.

Далее выполняются обыкновенные жордановы исключения:

·        на месте разрешающего элемента ставится 1

·        элементы строки, кроме разрешающей, записываются с обратным знаком

·        элементы столбца, кроме разрешающего, остаются без изменений

·        остальные коэффициенты считаются по правилу прямоугольника

Итерации следует повторять до тех пор, пока элементы в столбце свободного члена не будут неотрицательными.

2.     В строке  находим , а разрешающая строка находится как .

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

 

ЭЛЕМЕНТЫ ТЕОРИИ ДВОЙСТВЕННОСТИ

 

1.     Построение двойственных задач.

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


 

1. Каждому ограничению типа равенства и неравенства ставится в соответствие двойственная переменная

1.

2. Если исходная задача была на минимум, то двойственная будет на максимум:

2.

3.

3.

4.

4.

5.

5.

6.

6.

          Двойственная и прямая задачи взаимосвязаны.

 

Лемма (критерий оптимального решения прямой и двойственной задач). Пусть - допустимые решения соответственно прямой и двойственной задач. И если выполняется условие  , то эти решения являются оптимальными.

          Без ограничения общности рассмотрим задачу в стандартной форме записи:

 (3) - (4)

          Построим двойственную задачу:

 (5)

 (6) – (7)

 

          Следовательно,

 (8)     (9).

Откуда следует:

 

 (10)

(11)

          Докажем, что эти решения являются оптимальными.

Доказательство.

          Предположим противное. Пусть существует решение задачи (1)  (12).

Объединяя (1) и (12), получим:

 (13)

Откуда следует:

 (14), что противоречит (11). Значит, предположение было сделано неверно, т. е. другого  не существует.

          Приведем доказательство для двойственной задачи. Пусть существует решение  (15).

Объединяя (1) и (15), получим:

 (16) и  (17).

Получили, что неравенство (17) противоречит (12), т. е.  не является оптимальным решением.

Лемма доказана.

          На этом правиле основан симплекс – метод.

 

2.     Двойственный симплекс – метод.

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

Для ограничений (3) введем дополнительные переменные  и разрешим полученные уравнения относительно этих базисных переменных:

.

         

 

 

 

 

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

.

          В двойственной симплекс- таблице уравнения для прямой задачи записываем по строкам, а для двойственной – по столбцам. Алгоритм же двойственного симплекс – метода соответствует алгоритму решения задач на минимум:

 

1.     .

a)     нахождение допустимого решения двойственной задачи

b)    нахождение допустимого и одновременно оптимального решения прямой задачи

2.

3.     , иначе см. пункт 9.

4.     , иначе см. пункт 11.

5.     .

6.    

                    

                     .

7.    

    

8.     , переходим на пункт 3.

9.     Находим дополнительное и одновременно оптимальное решение:

, иначе см. пункт 12.

10. , пункт 6. Иначе см. пункт 13.

11.  Задача линейного программирования не имеет смысла, либо не имеет решения, а ДЗЛП не имеет решения.

12.  .

 

 

13.  Задача линейного программирования не имеет решения. ДЗЛП не имеет решения, либо не имеет смысла.

14.  Конец.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

 

РЕШЕНИЕ ЗАДАЧ В ОБЩЕЙ ФОРМЕ ЗАПИСИ И ФОРМЫ НАХОЖДЕНИЯ РЕШЕНИЯ

 

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

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

          Симплекс- метод предполагает не отрицательность переменных в исходной задаче (это эквивалентно ограничениям неравенствами в двойственной задаче). Если же переменные неопределенного знака, это эквивалентно ограничениям - равенствам в двойственной задаче.

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

          Если имеют место ограничения - равенства в двойственной задаче, то 0-столбец для двойственной задачи переводится в 0-строку. Строка тоже вычеркивается и записывается уравнение для переменной в прямой задаче.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Просмотрено: 0%
Просмотрено: 0%
Скачать материал
Скачать материал
Скачать материал

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 937 469 материалов в базе

Скачать материал

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

  • Скачать материал
    • 26.01.2022 83
    • DOCX 676.5 кбайт
    • Оцените материал:
  • Настоящий материал опубликован пользователем Морозов Николай Петрович. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

    Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

    Удалить материал
  • Автор материала

    Морозов Николай Петрович
    Морозов Николай Петрович
    • На сайте: 11 месяцев
    • Подписчики: 0
    • Всего просмотров: 159271
    • Всего материалов: 899

Ваша скидка на курсы

40%
Скидка для нового слушателя. Войдите на сайт, чтобы применить скидку к любому курсу
Курсы со скидкой