АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Модифицированные Жордановы преобразования

Читайте также:
  1. II. Элементарные преобразования. Эквивалентные матрицы.
  2. III ПРЕОБРАЗОВАНИЯ ПРИ ПОЛОВОМ СОЗРЕВАНИИ
  3. Аграрные преобразования в деревне
  4. Алгебраические преобразования
  5. Базовые технологии преобразования информации
  6. Билет 12 Различные уравнения прямой на плоскости, геометрический смысл параметров. Формула преобразования координат вектора при переходе к новому базису
  7. Билет 29Приведение квадратичной формы к каноническому виду с помощью ортогонального преобразования переменных.
  8. Второе важное обстоятельство - преобразования Галилея меняют вид уравнений Максвелла
  9. Выбрав любой ненулевой элемент сделать шаг жордановых исключений
  10. Выбрать разрешающий элемент (правило предыдущей теоремы), сделать шаг жордановых исключений. Получить новое опорное решение. Вернуться на шаг 2.
  11. Геометрические преобразования точек и отрезков. Однородные координаты
  12. Глава 14. Россия в конце XVII - первой четверти XVIII в. Петровские преобразования.

Или метод последовательного улучшения плана. Метод предназначен для решения общей задачи линейного программирования.

Пусть имеем следующую задачу:

, (1)

с системой ограничений следующего вида:

. (2)

Разрешим эту систему относительно переменных :

. (3)

Векторы условий, соответствующие , образуют базис. Перемен­ные назовем базисными переменными. Остальные переменные задачи – небазисные.

Целевую функцию можно выразить через небазисные переменные: .

Если приравнять небазисные переменные нулю ,

то соответствующие базисные переменные примут значения .

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

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

Построение опорного плана. Пусть необходимо решить задачу:

.

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

,

где .

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

  …. .…  
  …. ….
…. …. .… …. .… .… .… .…
  …. ….
…. ….
…. …. …. …. …. …. ….
…. ….
…. ….  

 

Правила выбора разрешающего элемента при поиске опорного плана.

1. При условии отсутствия “0-строк” (ограничений-равенств) и “сво­бодных” перемен­ных (т.е. переменных, на которые не наложено требованиенеотри­цатель­ности).

· Если в столбце свободных членов симплексной таблицы нет отрицательных элементов, то опорный план найден.

· Есть отрицательные элементы в столбце свободных членов, например . В такой строке ищем отрицательный коэф­фициент , и этим самым определяем разрешающий столбец . Если не найдем отри­цательный , то система ограничений несовместна (противо­речива).

· В качестве разрешающей выбираем строку, которой соответствует минимальное отношение: , где - номер разрешающей строки. Таким образом, - разрешающий элемент.

· После того, как разрешающий элемент найден, делаем шаг модифицированного жорданова исключения с направляющим элементом и переходим к следующей симплексной таблице.

2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.

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

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

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

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

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

– разрешающий (направляющий) элемент, строка – разрешающая.

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

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

 


1 | 2 | 3 | 4 | 5 | 6 | 7 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.)