Главная страница

КП_Тишинский. 5. Решение задачи линейного программирования вручную 10


Скачать 5.67 Mb.
Название5. Решение задачи линейного программирования вручную 10
АнкорКП_Тишинский.doc
Дата11.04.2018
Размер5.67 Mb.
Формат файлаdoc
Имя файлаКП_Тишинский.doc
ТипРешение
#17925
страница2 из 6
1   2   3   4   5   6

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



Симплекс метод является наиболее распространенным вычислительным методом, который может быть применен для решения любых задач ЛП как вручную, так и с помощью ЭВМ.

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

В результате оптимальное решение находят за конечное число шагов. Алгоритм симплекс-метода позволяет также установить является ли задача ЛП разрешимой.

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





где F(x) - целевая функция;  - базисные переменные; остальные переменные называются свободными.

Задача имеет m+n ограничений, среди них m ограничений типа равенства и n ограничений неотрицательности. По определению крайняя точка удовлетворяет n линейно-независимым ограничениям задачи как точным равенствам.

Алгоритм симплекс метода в случае неотрицательности свободных членов

  1. Переходим от системы неравенств к равенствам с помощью ослабляющих переменных.

  2. Находим единичные вектора условий, которые войдут в базис. Их должно быть столько, сколько уравнений в системе.

  3. Составляем симплекс таблицу.


Таблица 1 Общий вид симплекс таблицы

Сб

Б

В

















Q































1

0



0


















0

1



0











































0

0



1






Z




























L































    1. В первой строке записываем коэффициенты целевой функции.

    2. Коэффициенты ограничений переносятся в среднюю часть таблицы.

    3. Вносим свободные члены в третий столбец «В».

    4. Во второй столбец записываем базис (единичные вектора).

    5. Находим «Z» как сумму попарных произведений 1-го и 3-го столбцов.

    6. Предпоследнюю строку таблицы L находим как Сумму попарных произведений элементов первого столбца и соответствующего столбца средней части таблицы.

    7. Последнюю строку ∆ определяем как разность элементов предпоследней строки и 1-й строки (коэффициентов целевой функции).
      Величина «∆» - критерий оптимальности. Для задачи минимилизации оптимальным будет план, для которого все значения строки меньше или равны 0 (), а для задачи максимилизации план в котором все значения больше или равны 0 ().
      Если план не оптимален, то переходим к заполнению новой симплексной таблице.

  1. Находим разрешающий элемент.

    1. Для задачи максимализации выбираем столбец с максимальным по модулю ∆ среди отрицательных. А для задачи минимализации столбец с максимальным по модулю среди положительных. Такой столбец называется «Разрешающим»

    2. Для нахождения «Разрешающей» строки, значения элементов 3-го столбца («В») делим на значения соответствующих элементов Разрешающего столбца. Полученный результат записываем в последний столбец (Q).
      Среди полученных значений выбираем наименьшее. Строка, содержащая это число, и будет «Разрешающей».

    3. На пересечение Разрешающего столбца и разрешающей строки получаем «Разрешающий» элемент.

  2. В новой таблице меняем базисную переменную и соответственно поправляем 1-й столбец.

  3. Разрешающую строку делим на Разрешающий элемент и записываем на свои места.

  4. Обнуляем остальные элементы Разрешающего столбца.

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

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

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

Рисунок 2 7 Блок-схема алгоритма симплекс-метода

    1. 1   2   3   4   5   6


написать администратору сайта