В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров
Новости
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

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

Страница 4

4. Виды математических моделей двойственных задач

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

Н е с и м м е т р и ч н ы е з а д а ч и

(1) Исходная задача Двойственная задача

Zmin = CX; fmax = YA0;

AX = A0; YA £ С.

X ³ 0.

(2) Исходная задача Двойственная задача

Zmax = CX; fmin = YA0;

AX = A0; YA ³ С.

X ³ 0.

С и м м е т р и ч н ы е з а д а ч и

(3) Исходная задача Двойственная задача

Zmin = CX; fmax = YA0;

AX ³ A0; YA £ С.

X ³ 0. Y ³ 0.

(4) Исходная задача Двойственная задача

Zmax = CX; fmin = YA0;

AX £ A0; YA ³ С.

X ³ 0. Y ³ 0.

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

Найти минимальное значение линейной функции Z = 2x1 + x2 + 5x3 при ограничениях

x1 – x2 – x3 £ 4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

Рассматриваемая задача относится к симметричным двойственным задачам на отыскание минимального значения линейной функции. Для того чтобы было можно записать двойственную задачу, ее модель долж­на иметь вид (3). Переход осуществляется умножением первого не­равенства на -1.

Исходная задача:

Zmin = 2x1 + x2 + 5x3 при ограничениях

-x1 + x2 + x3 ³ -4,

x1 – 5x2 + x3 ³ 5, xj ³ 0 (j = 1, 2, 3).

2x1 – x2 + 3x3 ³6,

Двойственная задача:

fmin = -4x1 + 5x2 + 6x3 при ограничениях

-y1 + y2 + 2y3 £ 2,

y1 – 5y2 - y3 £ 1, yi ³ 0 (i = 1, 2, 3).

2y1 + y2 + 3y3 £ 5,

Приведем без доказательства следующую теорему. Теорема 1.1. Если при подстановке компонент оптимального пла­на в систему ограничений исходной задачи i-e ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.

Если i-я компонента оптимального плана двойственной задачи по­ложительна, то i-e ограничение исходной задачи удовлетворяется ее оптимальным решением как строгое равенство.

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

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

Переход к двойственной задаче не обязателен, так как если рассмо­треть первую симплексную таблицу с единичным дополнительным ба­зисом, то легко заметить, что в столбцах записана исходная задача, а в строках - двойственная. Причем оценками плана исходной задачи являются Сj а оценками плана двойственной задачи – bi. Решим "двойственную задачу по симплексной таблице, в которой записана ис­ходная задача; найдем оптимальный план двойственной задачи, а вместе с ним и оптимальный план исходной задачи. Этот метод носит на­звание двойственного симплексного метода,

Пусть необходимо решить исходную задачу линейного программиро­вания, поставленную в общем виде: минимизировать функцию Z =СХ при АХ = A0, Х ³ 0. Тогда в двойственной задаче необходимо максимизировать функцию f = YA0 при YA £ С. Допустим, что выбран такой базис D = (A1, А2, ., Аi, ., Аm), при котором хотя бы одна из компонент вектора Х = D-1 A0 = (x1, x2, ., xi, ., xm) отрицатель­ная (например, xi < 0), но для всех векторов Aj выполняется соотно­шение Zj – Cj £ 0 (i = 1,2, ., n). Тогда на основании теоремы двойственности Y = Сбаз D-1 - план двойственной задачи. Этот план не оптимальный, так как, с одной стороны, при выбранном бази­се X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны, оценки оптимального плана двой­ственной задачи должны быть неотрицательными.

Таким образом, вектор Аi, соответствующий компоненте xi < 0, следует исключить из базиса исходной задачи, а вектор, соответствую­щий отрицательной оценке,— включить в базис двойственной задачи.

Для выбора вектора, включаемого в базис исходной задачи, просмат­риваем i-ю строку: если в ней не содержатся xij < 0, то линейная функция двойственной задачи не ограничена на многограннике реше­ний, а исходная задача не имеет решений. Если же некоторые xij < 0, то для столбцов, содержащих эти отрицательные значения, вычисля­ем q0j= min (xi/xij) ³ 0 и определяем вектор, соответствующий max q0j(Zj — Cj) при решении исходной задачи на минимум и min q0j(Zj — Cj) при решении исходной задачи на максимум. Этот вектор и включаем в базис исходной задачи. Вектор, который необ­ходимо исключить из базиса исходной задачи, определяется направ­ляющей строкой.

Если q0j= min (xi/xij) = 0, т. е. xi = 0, то xij берется за раз­решающий элемент только в том случае, если xij > 0. Такой выбор раз­решающего элемента на данном этапе не приводит к увеличению коли­чества отрицательных компонент вектора X. Процесс продолжаем до получения Х ³ 0; при этом находим оптимальный план двойственной задачи, следовательно, и оптимальный план исходной задачи.

В процессе вычислений по алгоритму двойственного симплексного метода условие Zj – Cj £ 0 можно не учитывать до исключения всех хi < 0, затем оптимальный план находится обычным симплексным ме­тодом. Это удобно использовать, если все хi < 0; тогда для перехода к плану исходной, задачи за одну итерацию необходимо q0j определить не по минимуму, а по максимуму отношений, т. е. q0j= max (xi/xij) > 0.

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

6. Список используемой литературы

1. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. «Финансы и статистика», 1998 г.

2. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. «Наука», 1980 г.

Название: Двойственный симплекс-метод и доказательство теоремы двойственности
Раздел: Математика
Дата публикации: 2007-01-22 12:29:40
Прочтено: 19571 раз

1 2 3 [4]

скачать реферат скачать реферат

Новинки
Интересные новости


Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2020 textreferat.com