Студопедия

КАТЕГОРИИ:

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



Симплекс- метод решения задачи линейного программирования. Симплекс- таблицы.




Читайте также:
  1. Cоциологический анализ электорального процесса: проблемы и методы исследования, сферы применения результатов
  2. I. Невербальные методы оценки.
  3. I. Порядок заполнения формы разрешения на строительство
  4. II. 1. Методические указания к выполнению контрольных заданий
  5. II.2. Методика построения напорной и пьезометрической линий
  6. SWOT-анализ и методика его использования. Стратегический анализ, PEST-анализ, SNW-анализ в менеджменте.
  7. А Классификация и общая характеристика основных методов контроля качества.
  8. А) допомозі Німеччини – застосуванню насильницьких методів наведення порядку та дисципліни
  9. А) метод наблюдения
  10. А) понятие и задачи

Симплекс метод разрабатывался применительно к задачам линейного программирования, в которых множество решений D представляло собой симплекс в пространстве Rn т.е. D={x=Rn| , }, где

n- мерным симплексом Sn называется выпуклая оболочка n- точек (x1,x2,x3,…,xn) не лежащих на одной (n-2) мерной плоскости.

Симплекс- это n- мерный выпуклый многогранник имеющий в точности n- вершин.

Решение соответствующей исходной точки называется начальным решением.

Базисом матрицы А называется набор m линейно независимых столбцов.

А матрица размерности (mxn)

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

Для решения данной задачи необходимо выполнить следующие шаги:

Шаг 1: Инициализация

Разложим по исходному базису B={Aj1, Aj2,…., Ajm} небазисные вектор- столбцы матрицы А, т.е. найти координаты xj=B-1 b, вектор- столбцов Аi в базисе В. Разложение базисных вектор- столбцов известны xij=Ej. Также известны значения базисных переменных соответствующие базису В.

Шаг 2. Условия оптимальности.

Для каждого j от 1 до n вычислить симплекс- разность.

Если все симплекс- разности больше 0, то процесс решения задачи окончен и решение оптимальное, иначе перейти к шагу 3.

Шаг 3. Условие отсутствия решения задачи.

Выяснить существует ли хотя бы одна симплекс разность меньше 0.в этом случае процесс решения задачи окончен. Целевая функция задачи не ограничена. Если существует, то перейти к шагу 4.

Шаг 4: Итерация

Выбрать симплекс разность меньше 0 и с условием .

Соответствующие вектор столбцу xj небазисная переменная х вводится в базис. Вычислить отношение для всех i для которых хit>0 и найти минимальное из этих отношений.

Соответствующие k-ой строке матрицы А текущая базисная переменная выводится из базиса, при этом t- ая вводится в базис переменная принимает значение

и выполняется шаг 2.

Симплекс- таблица

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

симплекс-таблица представляет собой расширенную матрицу системы ограничений с некоторыми дополнительными столбцами и строками.



Симплекс- таблица размерности (m+1)*(n+2)

m- количество базисных переменных;

n- количество всех переменных.

M=

YB<m+1> CB<m+1>
- -

Построение симплекс-таблицы для задачи ЛП вида:

базисные переменные

( )- решение является допустимым и базисным, а исходная базисная матрица является единичной.

Начальное заполнение таблиц будет иметь вид:

YB CB X1 X2 …. Xn Xn+1 Xm+n
n+1 b1 a11 a12  
n+2 b2 a21 a22  
….. ….. …. ….. …..   ….. ….. …..
n+m bm am1 am2  
      …..

Столбец таблицы который вводится в базис называется ведущим столбцом.

Строка таблицы соответствующая вектору выводимому из базиса называется ведущей строкой.

Элемент стоящий на пересечении ведущей строки и ведущего столбца называется ведущим элементом.

Пересчет симплекс- таблицы по закону:

Элемент ведущей строки делим на ведущие элементы.



Все элементы в ведущем столбце ,кроме ведущего заменяем не 0.

Заменяем номер ведущей строки на номер ведущего столбца.

Если в предыдущей таблице есть отрицательная симплекс- разность, то решение не является оптимальным, необходимо пересчитать таблицу еще раз.

 

2. Геометрическая интерпретация решения задачи линейного программирования.

Определение. Непустое множество планов общей (ос­новной) задачи линейного программирования называется многогранником решений.

Свойство. Если основная задача линейного программи­рования имеет оптимальный план, то максимальное значение целевая функция принимает в одной из вершин многогран­ника решений.

Вершину многогранника решений, в которой целевая фун­кция принимает максимальное значение, найти не сложно, если задача содержит не более двух переменных (в обшем случае задача, записанная в основной форме, содержит не более двух свободных переменных, то есть п-r < 2, где п -число переменных, r— ранг матрицы, составленной из ко­эффициентов в системе ограничений задачи).

Найдем решение задачи, состоящей в определении мак­симального значения функции

F = c1x1+c2x2 (*)

при условиях

(1)

(2)

Каждое из неравенств (1), (2) геометрически опреде­ляет полуплоскость соответственно с граничными прямыми ai1x1 + ai2x2 =bi , i = 1,...k, x1 = 0, х2 = 0. Областью решений системы является множество точек, принадлежащих всем полуплоскостям, называемое в двумерном случае много­угольником решений.

Исходная задача линейного программирования состоит в нахождении вершины многоугольника решений, в которой целевая функция (*) принимает максимальное значение. Такая вершина существует тогда, когда многоугольник ре­шений не пуст и на нем целевая функция ограничена сверху. Для определения этой вершины построим линию уровня с1х1 + с2х2 = h, проходящую через многоугольник решений, и будем перемещать ее в направлении вектора С = (c1c2), орто­гонального ей, до тех пор пока она не пройдет через послед­нюю общую точку с многоугольником решений. Координаты этой точки и определяют оптимальный план задачи.

Отметим, что нахождение минимального значения линейной функции при данной системе ограничений отличается от нахож­дения ее максимального значения при тех же ограничениях лишь тем, что линия уровня с1х2 + c2x2 = h перемещается не в направ­лении вектора С = (с1, с2), а в противоположном направлении.

 


Дата добавления: 2015-04-18; просмотров: 87; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты