Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Gt; во-вторых, когнитивной оценкой (cognitive appraisal), которую человек дает событию, требующему разрешения.
  2. Hешаем задачу
  3. I. Задачи настоящей работы
  4. I. Решение логических задач средствами алгебры логики
  5. I. Цели и задачи проекта
  6. II. Объем и сроки выполнения задач в рамках проекта
  7. II. Основные цели и задачи Программы, срок и этапы ее реализации, целевые индикаторы и показатели
  8. II. Решение логических задач табличным способом
  9. II. Упражнения и задачи
  10. II. Упражнения и задачи

Рассмотрим алгоритм решения задач симплексным методом[17].

1. Математическая модель задачи должна бать канонической. Если она неканоническая, то ее надо привести к каноническому виду.

2. Находим исходное опорное решение и проверяем его на оптимальность. Для этого заполняем симплекс-таблицу. Все строки таблицы 1-го шага, за исключением строки Dj (индексная строка), заполняем по данным системы ограничений и целевой функции.

Симплексная таблица имеет следующий вид:

сi Базисная переменная (БП) с1 с2 ¼ сm сm+1 ¼ сn f(`X)
x1 x2 ¼ xm xm+1 ¼ xn b1
c1 x1 ¼ h1, m+1 ¼ h1n l1
c2 x2 ¼ h2, m+1 ¼ h2n l2
¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼ ¼
cm xm ¼ hm, m+1 ¼ hmn lm
Dj ¼ Dm+1 ¼ Dn f(`X1)

 

Индексная строка (Dj) для переменных находится по формуле

и для свободного члена по формуле

.

При этом возможны следующие случаи решения задачи на максимум:

- если все оценки Dj ³ 0, то найденное решение оптимальное;

- если хотя бы одна оценка Dj £ 0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f(X) ® ¥, т.е. целевая функция не ограничена в области допустимых решений;

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

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

Пусть одна оценка Dk £ 0 или наибольшая по абсолютной величине Dk £ 0, тогда k-й столбец принимают за ключевой (разрешающий). За ключевую (разрешающую) строку принимают ту, которой соответствует минимальное отношение свободных членов (bi) к положительным коэффициентам k-го столбца. Элемент, находящийся на пересечении ключевых строки и столбца, называют ключевым (разрешающим) элементом.



3. Заполнение симплексной таблицы 2-го шага:

- переписывается ключевая строка, разделив ее элементы на ключевой элемент;

- заполняют базисные столбцы;

- остальные коэффициенты таблицы находят по правилу «прямоугольника». Оценки можно считать по приведенным выше формулам или по правилу «прямоугольника». Получается новое опорное решение, которое проверяется на оптимальность и т.д.

Примечание. Если целевая функция f(X) требует нахождения минимального значения, то критерием оптимальности задачи является неположительность оценок Dj при всех .

Правило «прямоугольника» состоит в следующем. Пусть ключевым элементом 1-го шага является элемент 1-й строки (m+1)-го столбца h1, m+1. Тогда элемент i-й строки (m+2)-го столбца 2-го шага, который обозначим , по правилу «прямоугольника» определяется по формуле

,

где h1, m+1, hi, m+1, hi, m+2 – элементы 1-го шага.

 


Дата добавления: 2014-12-03; просмотров: 28; Нарушение авторских прав







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