Решение завдання лінійного программирования

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Рішення завдання лінійного программирования.

Розглянемо завдання лінійного программирования

[pic](1)

Теорему. Якщо безліч [pic] планів завдання (1) не порожньо і цільова функція [pic] згори обмежена у цьому безлічі, то завдання (1) має решение.

Теорему. Якщо безліч [pic] допустимих планів має крайні крапки й завдання (1) має рішення, але серед крайніх точок знайдеться оптимальная.

Метод винятку Жордана-Гаусса системі лінійних уравнений.

Більшість із існуючих про чисельні методів вирішення завдань лінійного програмування використовує ідею приведення системи лінійних уравнений

[pic] що у матричної формі записується як [pic], до більш зручного виду з допомогою з так званого методу Жордада-Гаусса.

У першому рівнянні системи відшукується коефіцієнт [pic], відмінний від нуля. З допомогою цього коефіцієнта звертаються до нуль коефіцієнти при перемінної [pic] у решті рівняннях системи. І тому перше рівняння збільшується на число [pic] і додається до рівнянню з номером [pic], [pic]. Потім перше рівняння ділиться на число [pic]. Це перетворення називається елементарним перетворенням. Отримана еквівалентна система має тим властивістю, що змінна [pic] присутній у першому рівнянні, і з коефіцієнтом 1. Змінна [pic] називається базисної переменной.

Аналогічну операцію відбувається по черзі з кожним рівнянням системи; у своїй щоразу перетворюються все рівняння і виконується список базисних переменных.

Результатом застосування методу Жордада-Гаусса є що: або встановлюється, що систему несовместна, або проявляються й відкидаються все «зайві» рівняння; у своїй підсумкова система рівнянь має вид

[pic], [pic], де [pic] - список номерів базисних змінних, [pic] - безліч номерів небазисных змінних. Тут [pic] - ранг матриці [pic] коефіцієнтів вихідної системи уравнений.

Отриману системи рівнянь називають наведеної системою, відповідної безлічі [pic] номерів базисних переменных.

Симплекс-метод.

Симплекс -метод, метод послідовного поліпшення плану, в час основним методом вирішення завдань ЛП.

Розглянемо канонічну завдання ЛП

[pic](2) де вектори [pic], матриця [pic] і [pic]. Безліч планів в завданню (2) будемо позначати через [pic] і припускати, що це кутові точки [pic] є невырожденными. [pic], де вектор [pic] визначається за формулою [pic].

Теорему. Якщо кутовий точці [pic] виконується умова [pic], то [pic] - вирішення завдання (2).

Теорему. А, щоб кутова точка [pic] була рішенням завдання (2), необхідне й досить, щоб у ній виконувалося умова [pic].

Алгоритм симплекс-метода.

Перехід зі старої кутовий точки [pic] на нову кутову точку [pic] полягає, по суті, лише зміні базисної матриці [pic], у якому замість вектора [pic] вводиться вектор [pic]. Нова базисна матриця може бути тепер використана для обчислення базисних компонентів вектора [pic]. Отже, алгоритм симплекс-метода то, можливо представлено наступній форме.

Крок 0. Поставити цільової вектор [pic], матрицю умов [pic], вектор обмежень [pic] і безліч базисних індексів [pic]. Сформувати базисну матрицю [pic] і вектор [pic].

Крок 1. Обчислити матрицю [pic] і вектор [pic].

Крок 2. Обчислити вектор потенціалів [pic] з оцінкою [pic].

Крок 3. Якщо [pic] всім [pic], то зупинитися: вектор [pic] - базисний вектор оптимального плану; інакше перейти на крок 4.

Крок 4. Вибрати довільний індекс [pic] і обчислити вектор [pic].

Крок 5. Якщо [pic], то зупинитися: [pic]; інакше перейти на крок 6.

Крок 6. Сформувати безліч індексів [pic] і обчислити [pic].

Крок 7. У безлічі [pic] індекс [pic] замінити на індекс [pic], в матриці [pic] - вектор [pic] - на вектор [pic], в векторі [pic] - компоненту [pic] на [pic]. Перейти на крок 1.

ПоказатьСвернуть
Заполнить форму текущей работой