Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Метод равномерного поиска. | Метод поразрядного приближения | Метод деления отрезка пополам (или метод дихотомии). | Метод квадратичной интерполяции | Метод золотого сечения | Численные методы поиска экстремумов функций многих переменных | Метод координатного спуска | Градиентный метод | Постановка задачи. Графический метод | Графический метод решения задачи линейного программирования. |


Читайте также:
  1. I. Коммуникативные игры, в основе которых лежит методический прием ранжирования.
  2. I. Новые нормативные и методические документы в области воздухоохранной деятельности
  3. I. Организационно-методический раздел
  4. II. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ
  5. IV. МЕТОДИЧЕСКАЯ ЧАСТЬ ПРОЕКТА
  6. IV. МЕТОДИЧЕСКАЯ ЧАСТЬ ПРОЕКТА
  7. Quot;НЕДЕЛАНИЕ". ОСТАНОВКА ВНУТРЕННЕГО ДИАЛОГА. МЕТОДЫ

Будем исследовать задачу линейного программирования в КАНОНИЧЕСКОЙ ФОРМЕ:

АХ = В, Х³ 0, f = (с, х) -> min.

При этом пусть A - матрица размером r*n, где r - число независимых уравнений, n-число переменных, r<n, rang(А)=r.

Заданная система имеет бесконечно много решений, при этом множество решений системы образует пространство размерности n-r. Чтобы его описать, надо выбрать n-r свободных переменных, тогда оставшиеся r переменных будут называться базисными и выражаться через свободные переменные.

Договоримся, что свободные переменные имеют номера с r+1 до n-ого, т.е. базисными переменными являются x1,...,xr.

 
 

Выразив базисные переменные через свободные, линейную систему сведем к виду:

Если свободным переменным придать значение, равное 0, то получим решение: (b1,b2,...,br,0,0,...,0).

В каком случае этот набор будет допустимым решением задачи? Так как хi должны быть неотрицательными, то и все bi должны быть неотрицательными. Такое решение задачи называется базисным решением. Базисных решений много. Геометрический смысл базисного решения состоит в том, что это координаты одной из вершин многогранника допустимых значений в n-мерном пространстве. Если задача корректна, то одно из базисных решений задачи будет оптимальным. Следовательно, перебирая все вершины и вычисляя значение целевой функции в каждой из них, мы можем найти решение задачи. Однако, данный процесс очень трудоемок: для нахождения одного базисного решения придется решать систему уравнений r*n (а количество базисных решений равно числу сочетаний из n по r, т.е. весьма велико).

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


Дата добавления: 2015-08-27; просмотров: 53 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Двойственная задача| Описание симплекс-метода.

mybiblioteka.su - 2015-2024 год. (0.011 сек.)