Табличная реализация симплекс – метода

Табличная реализация симплекс – метода

Постановка задачки ЛП.

Модель задачки математического программирования включает:

1) Совокупа неведомых величин Х=(x1, x­­­2, …, xn), действуя на которые, систему можно улучшать. Их именуют планом задачки;

2) Мотивированную функцию z(x) [f(x)];

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

План Х, удовлетворяющий системе ограничений задачки, именуется допустимым.

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

Лучший план обозначается Х*, а экстремальное значение мотивированной функции – z(Х*)=z*

Модель задачки ЛП Табличная реализация симплекс – метода может быть записана в одной из приведённых ниже форм.

1. Общая, либо случайная, форма записи:

2. Симметричная, либо стандартная, форма записи:

3. Каноническая, либо основная, форма записи:

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

По мере надобности задачку минимизации можно Табличная реализация симплекс – метода поменять задачей максимизации, и напротив. Разумеется, что малое значение функции z(x) равно наибольшему значению функции -z(x), взятому с обратным знаком, т.е.

min z(x)=-max (-z(x))

Неравенство типа оковём умножения левых и правых частей на -1 можно перевоплотить в неравенство типа , и напротив.

Ограничения Табличная реализация симплекс – метода – неравенства

преобразуются в ограничения – равенства оковём добавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных xn+1≥0:

.

В случае необходимости ограничение – равенство

можно записать в виде системы неравенств:

­Если в ЗЛП какая-то переменная xk не подчинена условию неотрицательности, её подменяют разностью 2-ух других неотрицательных переменных и :

.

Симплекс – способ

Существует универсальный метод решения задач линейного программирования Табличная реализация симплекс – метода, именуемый симплекс – способом.

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

Для построения симплекс – способа решения задач ЛП надлежащие модели должны быть представлены в канонической форме.

Построение исходного опорного плана.

1 случай. В системе ограничений Табличная реализация симплекс – метода имеется единичный неотрицательный базис, т.е. ЗЛП имеет вид:

max z=c1x1+c2x2+…+cnxn;

Без ограничения общности можно положить, что базовыми являются 1-ые m переменные. Тогда исходный опорный план содержит m базовых и (n-m) свободных переменных. Свободные переменные равняются нулю, а базовые – свободным членам. Получаем исходный опорный план Табличная реализация симплекс – метода

2 случай. Система ограничений имеет вид:

Приводим задачку к каноническому виду, добавляя к левым частям неравенств дополнительные неотрицательные переменные xn+1, xn+2, …, xn+m. Получим систему ограничений

,

в какой базовыми являются переменные xn+1, …, xn+m, а свободными x1, x2, …, xn.

В мотивированную функцию дополнительные переменные вводятся с коэффициентами, равными нулю:

z=c1x1+c Табличная реализация симплекс – метода2x2+…+cnxn+0∙xn+2+…+0∙xn+m

3 случай. Система ограничений имеет вид:

(1)

Приводим задачку к каноническому виду, вычитая из левых частей неравенств дополнительные неотрицательные переменные xn+1­, xn+2, …, xn+m. Получим систему ограничений:

, (2)

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

(3)

Искусственные переменные Табличная реализация симплекс – метода ω1, …, ωm сейчас станут базовыми, а переменные x1, x2, …, xn+m – свободными.

В мотивированную функцию z искусственные переменные входят с коэффициентом M со знаком “+”, если эта задачка минимизации, и со знаком “-”, если – максимизации. При всем этом M полагается довольно огромным положительным числом. Т.о. мотивированная функция имеет вид:

z=c1x1+…+cnxn Табличная реализация симплекс – метода±Mω1±Mω2±…±Mωm.

Перевоплощенная схожим образом ЗЛП именуется M-задачей.

В рациональном плане все искусственные переменные ωi должны быть равны нулю, т.к. в начальной задачке таких переменных нет. Дополнительные переменные xn+1, …, xn+m могут иметь положительные значения.

Табличная реализация симплекс – способа

Условия задачки заносятся в таблицу

A1 A2 An
БП x1 x2 xn
c Табличная реализация симплекс – метода1 c2 cn
Рабочее поле
Индексные оценки, Δj Δ0 Δ1 Δ2 Δn
z(x0)

В столбец БП заносятся базовые переменные.

Столбец СБсодержит коэффициенты мотивированной функции, стоящие при базовых переменных.

Столбец А0(базовые значения) содержит значения БП в опорном плане.

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

Индексные Табличная реализация симплекс – метода оценки определяются формулами:

Признак оптимальности опорного плана:

1. если начальная задачка на maxи для некого опорного плана все индексные оценки Δj≥0, то таковой план оптимален.

2. если начальная задачка на min и для некого опорного плана все индексные оценки Δj≤0, то таковой план оптимален.

Переход к нехудшему опорному плану.

Если в таблице Табличная реализация симплекс – метода все Δj≥0 (max) {Δj≤0 (min)}, то исходный опорный план Х0 оптимален. Если же есть Δj<0 {Δj>0}, то находим посреди их (некорректных индексных оценок) наивысшую по модулю:

Δj<0

{Δj>0}

Столбец j0 именуется разрешающим. Переменную xj0, подобающую разрешающему столбцу, следует ввести в базис.

Для определения переменной, выводимой из базиса, находят симплексные дела: для Табличная реализация симплекс – метода этого делим соответственно элементы A0 на положительные коэффициенты Aj0. Посреди симплексных отношений определяют меньшее; оно и укажет строчку, в какой содержится исключаемая из базиса переменная x­i0. Строчка i0, соответственная наименьшему симплексному отношению, именуется разрешающей. Элемент, стоящий на скрещении разрешающего столбца и разрешающей строчки, также именуется разрешающим.

Строим новейшую симплексную Табличная реализация симплекс – метода таблицу по правилу:

1. элементы разрешающей i0-той строчки делим на разрешающий элемент;

2. все элементы разрешающего столбца j0 равны нулю (включая Δj0), кроме

3. столбцы, надлежащие оставшимся БП остаются без конфигураций;

4. другие элементы получаем по правилу прямоугольника:


Элементы ? = (произведению частей по главной диагонали минус произведение частей по побочной диагонали), деленному на разрешающий элемент Табличная реализация симплекс – метода.

Контроль вычислений частей индексной строчки осуществляется по формулам:

Признак неограниченности мотивированной функции:

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


tablica2-dinamika-otvetov-na-vopros-kak-izmenitsya-socialno-ekonomicheskaya-situaciya-v-belarusi-v-blizhajshie-godi-.html
tablice-3-kalendarnij-plan-okazaniya-uslug-i-obshie-usloviya-provedeniya-konkursa.html
tablichnaya-realizaciya-simpleks-metoda.html