Элементы матричной алгебры




НазваниеЭлементы матричной алгебры
страница14/24
Дата публикации23.06.2013
Размер1.64 Mb.
ТипДокументы
lit-yaz.ru > Математика > Документы
1   ...   10   11   12   13   14   15   16   17   ...   24
^

Глава 4. Симплексный метод.

  • 4.1. Основы симплексного метода



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

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

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

    Такой целенаправленный перебор позволит сократить число шагов при отыскании оптимального решения. Поясним это на графическом примере(рис 4.1)

    Рис.4.1

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

    Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования – симплексного метода. Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем. Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.

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

    • ЗЛП приведена к каноническому виду, свободные члены ограничений не отрицательны ( )

    • известно исходное опорное решение;

    • система ограничений приведена к единичному базису исходного опорного решения.

    Прежде чем сформулировать критерий оптимальности симплексного метода и правило перехода к лучшему решению рассмотрим алгоритм вычислительной реализации этих элементов на примере

    Пример 4.1. Найти вектор , удовлетворяющий системе неравенств

    , (4.1)

    условиям неотрицательности (4.2)

    и обращающий функцию в максимум (4.3)

    Графическое решение этого примера было рассмотрено в разделе 3.5 (см. рис 4.2).

    Рис. 4.2

    Оптимальное решение находится в точке В(2,6) и Fmax =22.

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

    (4.4)



    Для нахождения первоначального базисного решения разобьем переменные на две группы– основные(базисные) и не основные (свободные). Так как коэффициенты перед введенными дополнительными переменными ( ), образуют единичную матрицу размерности (33), то система (4.4) приведена к единичному базису этих переменных и переменные можно взять в качестве основных на первом шаге решения задачи.

    I шаг. базисные переменные , свободные :

    Выразим базисные переменные через свободные :

    (4.5)

    Положив свободные переменные равными нулю, т. е. , получим опорное решение: , которое соответствует вершине О(0,0) многоугольника OABCD на рис. 4.2.

    Линейная функция выражена через свободные переменные: ,

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

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

    Другими словами должны выполняться неравенства:

    откуда (4.6)

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

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

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

    В результате получен новый набор базисных ( ) и свободных ( ) переменных.

    II шаг: базисные , свободные ( )

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

    (4.7)

    Второе опорное решение соответствует вершине А (0,4) на рис. 4.2. Выразим линейную функцию через свободные переменные этого шага:



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

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

    III шаг: базисные , свободные ( ).

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



    Опорное решение соответствует вершине B(2,6) многоугольника решений. Выразим целевую функцию через свободные переменные ( ): .

    Это выражение не содержит положительных коэффициентов при свободных переменных, поэтому значение является максимальным. Функцию невозможно увеличить переходя к новому опорному плану, т.е. является оптимальным.

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

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

    если в выражении линейной функции через свободные переменные имеются положительные коэффициенты при свободных переменных, то можно перейти к новому опорному решению с лучшим значение целевой функции, если выбрать для ввода в базис свободную переменную с положительным коэффициентом. Для определенности выбирается переменная с наибольшим положительным коэффициентом.
  • 1   ...   10   11   12   13   14   15   16   17   ...   24

    Похожие:

    Элементы матричной алгебры iconКурсовая работа по дисциплине «Информатика» на тему «Применение алгебры...
    Элементы алгебры высказываний. Примеры использования алгебры высказываний в информатике

    Элементы матричной алгебры iconКурсовая работа по информатике на тему: «применение алгебры высказываний в информатике»
    Алгебра – это наука, которая изучает множество некоторых элементов и действия (операции) над ними. Если элементы алгебры – натуральные...

    Элементы матричной алгебры iconКонспект урока на тему «Основы логики (повторение). Решение логических...
    Основы логики; познакомить учащихся с методами решения логических задач; формирование у учащихся практических умений и навыков решения...

    Элементы матричной алгебры iconМетод «от пролога к эпилогу»
    «все его элементы суть элементы смысловые» (Лотман Ю.). Исходя из этих положений, выделяем основные приемы, опробуем их на уроке

    Элементы матричной алгебры iconЭлементы радиочастотных линий передачи
    Элементы радиочастотных линий передачи: Учебно-методическое пособие по курсу «Устройства свч и антенны» / В. В. Паслен, Е. С. Нестругина....

    Элементы матричной алгебры iconДипломной практике «система управления ртк для обработки сложных поверхностей»
    Обычно изделия изготавливаются из мягких цветных металлов, пластика или дерева. Это могут быть элементы орнамента для декорирования...

    Элементы матричной алгебры iconУрок по геометрии в 8 классе на тему «теорема пифагора»
    Осуществление межпредметной связи алгебры с географией, историей, литературой, геометрией

    Элементы матричной алгебры icon15. Уроки алгебры Кирилла и Мефодия,10-11 класс
    МАрк sql. Автоматизированная информационно-библиотечная система. Версия для школьных библиотек

    Элементы матричной алгебры iconРабочая программа факультативного курса «Элементы статистики и теории вероятностей»
    «Элементы комбинаторики, статистики и теории вероятностей». Так как в этом году учащиеся 9 класса изучают программный материал по...

    Элементы матричной алгебры iconИсследование свойств алгебры множеств
    Цель работы: Изучение множества, его подмножеств и законов сочетания подмножеств, образующих алгебраическую систему, называемую булевой...



    Образовательный материал



    При копировании материала укажите ссылку © 2013
    контакты
    lit-yaz.ru
    главная страница