Двойственный симплекс-метод

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

Рубрика Математика
Вид задача
Язык русский
Дата добавления 21.08.2010
Размер файла 221,4 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Министерство образования и науки Украины

Днепропетровский Национальный Университет

Факультет электроники, телекоммуникаций и компьютерных систем

Кафедра АСОИ

Расчётная задача №5

«Исследование операций»

Выполнил: Ст. группы РС-05

Куликов Е.С.

Проверил:

Доцент кафедры АСОИ

Саликов В.А.

г. Днепропетровск 2007г.

Двойственный симплекс-метод

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

при условиях

(56)

Где

и среди чисел имеются отрицательные.

В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) - (56), так как среди его компонент имеются отрицательные числа.

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

Таким образом, можно найти:

На основе исходных данных составляют симплекс-таблицу, в которой некоторые элементы столбца вектора являются отрицательными числами. Если таких чисел нет, то в симплекс-таблице записан оптимальный план задачи (54) - (56), поскольку, по предположению, все . Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс-таблицы к другой до тех пор, пока из столбца вектора P0 не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)-й строки, т.е. для любого

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

, где

Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс-таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i-й строке симплекс-таблицы в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

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

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная с этапа 2.

Найти максимальное значение функции

при условиях:

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

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

Строим симплекс таблицу:

Итерация 0:

Базис

Решение

Оценка

-7

2

0

0

0

0

1

1

1

0

0

5

2

-3

0

1

0

6

3

-3

-1

0

0

5

3

-

Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент.Продолжаем наши действия

Итерация 1:

Базис

Решение

0

9

7

0

0

35

1

1

1

0

0

5

0

-5

-2

1

0

-4

0

2

3

0

5

18

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

Итерация 2:

Базис

Решение

0

1

0

0

0

0

0

1

0

0

0

5

Полученная симплекс-таблица удовлетворяет и условию оптимальности и условию допустимости, так как она, во-первых, не содержит отрицательных коэффициентов в -строке, а, во-вторых, в графе «Решение» все значения положительные.

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

,

Проверка ответа

Графический метод

Ответ:

Максимальное значение целевой функции равно

Получено оптимальное решение при


Подобные документы

  • Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.

    курсовая работа [219,4 K], добавлен 17.04.2013

  • Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.

    контрольная работа [66,3 K], добавлен 06.04.2012

  • Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.

    курсовая работа [65,3 K], добавлен 30.11.2010

  • Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.

    задача [26,1 K], добавлен 27.11.2015

  • Линейное программирование как наиболее разработанный и широко применяемый раздел математического программирования. Понятие и содержание симплекс-метода, особенности и сферы его применения, порядок и анализ решения линейных уравнений данным методом.

    курсовая работа [197,1 K], добавлен 09.04.2013

  • Системы линейных уравнений и интерпретация их решений как пересечение гиперплоскостей в n-мерном координатном пространстве. Размерность и подпространства линейного пространства. Оптимизационные задачи линейного программирования. Суть симплекс-метода.

    курсовая работа [132,2 K], добавлен 10.01.2014

  • Теоретические положения симплекс-метода и постоптимального анализа. Построение математической модели задачи. Нахождение ценностей ресурсов. Определение относительных и абсолютных диапазонов изменения уровней запасов дефицитных и недефицитных ресурсов.

    курсовая работа [86,7 K], добавлен 19.11.2010

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

    контрольная работа [484,7 K], добавлен 29.07.2013

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

    курсовая работа [37,2 K], добавлен 01.05.2011

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

    дипломная работа [351,2 K], добавлен 01.06.2015

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.