для самостоятельной работы

для самостоятельной работы

по дисциплине «Математические способы исследования операций»

для студентов специальности

«Информационные управляющие системы и технологии»

Утверждено

на заседании кафедры автоматических систем обработки инфы и управления Протокол № 1 от 29.08.2012

Киев 2012

Симплекс-метод. Методические указания для самостоятельной работы по дис­циплине «Математические способы исследования операций» для студентов специальности «Информационные управляющие системы и технологии» / Сост для самостоятельной работы.: Е.Г. Жданова. – К.: НТУУ “КПИ”, 2012. – 70 с.

Учебное издание

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

МетодичЕСКИЕ УКАЗАНИЯ

для самостоятельной работы

по дисциплине «Математические способы исследования операций»

для студентов специальности

«Информационные управляющие системы и технологии»

Составитель Жданова Лена Григорьевна

Ответственный редактор В.А. Тихонов

Рецензенты: C.Ф. Теленик

В.Н. Кузнецов


Методические указания содержат теоретические базы симплекс-метода – основного способа решения задач линейного программирования для самостоятельной работы. Приведены главные аксиомы линейного программирования, схемы алгоритмов симплекс-метода и табличного симплекс-метода. Рассмотрены способы нахождения исходного допустимого базового решения, особенные случаи использования симплекс-метода. Приведены примеры решения задач линейного программирования и задания для контрольных работ.

Содержание

1. Формы ЗЛП................................................................................................................................... 4

2. Эквивалентность разных форм ЗЛП............................................................................. 5

3. Главные характеристики ЗЛП.......................................................................................................... 8

4. Мысль симплекс для самостоятельной работы – способа......................................................................................................... 12

5. Перевоплощенная задачка....................................................................................................... 12

6. Метод перехода от 1-го ДБР к другому....................................................................... 14

7. Условие оптимальности ДБР................................................................................................ 16

8. Схема симплекс-метода......................................................................................................... 18

9. Табличный симплекс-метод.................................................................................................. 21

9.1. Схема табличного симплекс-метода...................................................................... 22

10. Примеры реализации табличного симплекс-метода................................................... 23

11. Искусственное изначальное решение.................................................................................. 34

11.1. М - способ...................................................................................................................... 35

11.2. Двухэтапный способ................................................................................................... 38

12. Вырожденность....................................................................................................................... 46

12.1 Вырожденное среднее решение................................................................... 46

12.2. Промежуточное вырожденное решение............................................................. 48

13. Другие рациональные решения........................................................................ 56

14. Неограниченность места решений и для самостоятельной работы мотивированной функции............................... 59

15. Отсутствие допустимых решений..................................................................................... 63

16.Задания для контрольной работы...................................................................................... 68

Перечень литературы...................................................................................................................... 70


1. Формы ЗЛП

Задачка математического программирования вида:

именуется задачей линейного программирования (ЗЛП).

Основными допущениями, принимаемыми при построении линейных моделей, является пропорцио­нальность, аддитивность, неотрицательность.

Зависимо от вида ограничений различают три главные формы ЗЛП.

ЗЛП вида (1)–(5) именуется общей ЗЛП.

ЗЛП вида:

именуется стандартной для самостоятельной работы ЗЛП. В матричном виде она записывается последующим образом:

где

ЗЛП вида:

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

Способ решения ЗЛП разработан для задачки в канонической форме.

2. Эквивалентность разных форм ЗЛП

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

Правила преобразования разных форм ЗЛП:

а) максимизация мотивированной функции эквивалентна минимизации для самостоятельной работы мотивированной функции ;

б) ограничение-неравенство «≤» при помощи введения неотрицательной переменной можно поменять системой:

где si – остаточная переменная;

в) ограничение-неравенство «≥» при помощи введения неотрицательной переменной можно поменять сис­темой:

где si – лишная переменная.

Остаточные и лишниие переменные именуются еще свободными, балансовыми, дополнительны­ми;

г) ограничение-равенство можно поменять 2-мя неравенствами:

д для самостоятельной работы) неравенство «≥» переводится в неравенство «≤» умножением его на –1.

е) m ограничений-равенств можно поменять на (m+1) неравенство:

ж) если на xj не накладывается ограничение не отрицательности, то, введя новые две неотрицатель­ные переменные xj+≥0, xj–≥0, начальную переменную xj можно исключить методом подмены: xj=xj+–xj–. Как следует, всегда найдутся для самостоятельной работы такие неотрицательные xj+, xj–, что их разность даст xj.

Пример 2.1

Привести ЗЛП к канонической форме:

z = 3x1 – x2 → max,

x1 + 2x2 ≥ 6,

– 2x1 + 7x2 ≥ 8,

3x1 – 8x2 ≤ 15,

– 4x1 + x2 = 10,

x1 , x2 ≥ 0.

Решение

Потому что 1-ое ограничение имеет символ “≥”, то в левую часть ограничения вводим сверхизбыточную переменную s1. Данное ограничение будет иметь вид для самостоятельной работы:

x1 + 2x2 – s1 = 6,

s1 ≥ 0.

2-ое ограничение также имеет символ “≥”, для приведения к канонической форме в левую часть ограничения вводим сверхизбыточную переменную s2:

– 2x1 + 7x2 – s2 = 8,

s2 ≥ 0.

Потому что третье ограничение имеет символ “≤”, то в левую часть ограничения добавляем остаточную переменную s3:

3x1 – 8x2 + s3 = 15,

s3 ≥ 0.

Потому что четвёртое ограничение имеет для самостоятельной работы символ “=”, то ограничение оставляем без конфигурации, не добавляя дополнительных переменных. Данное ограничение в канонической форме имеет начальный вид:

-4x1 + x2 = 10.

Итак, в канонической форме данная ЗЛП будет смотреться так:

z = 3x1 – x2 + 0s1 + 0s2 + 0s3→ max

x1 + 2x2 – s1 = 6,

–2x1 + 7x2 – s2 = 8,

3x1 – 8x2 + s3 = 15,

–4x1 + x для самостоятельной работы2 = 10,

x1, x2, s1, s2, s3 ≥ 0.

Пример 2.2

Привести ЗЛП к ЗЛП в канонической форме, в какой направление оптимизации - максимизация:

z = 3x1 – 5x2 → min,

4x1 + 7x2 ≤ 6,

5x1 + 2x2 ≥ 8,

3x1 – 3x2 ≥ 5,

x1 , x2 ≥ 0.

Решение

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

z = –3x1 + 5x2 + 0s1 + 0s2 + 0s3→max,

4x1 + 7x2 + s1 = 6,

5x1 + 2x2 – s2 = 8,

3x1 – 3x2 – s3 = 5,

x1, x2, s1, s2, s3 ≥ 0 .

Пример 2.3

Привести к канонической форме ЗЛП.

max z = 13x1 – 20x2,

x1 + 2x2 ≤ 6,

-2x1 + 7x2 ≥ 8,

x1 , ≥ 0,

x2 0.

Решение

В данном случае на переменную для самостоятельной работы x2 не накладывается ограничение неотрицательности. Введя две новые неотрицательные переменные x2+≥0, x2–≥0, начальную переменную x2 можно исключить оковём подмены: x2 = x2+ – x2–.

Мотивированная функция будет иметь вид:

max z = 13x1 – 20(x2+ – x2–).

После раскрытия скобок:

max z = 13x1 – 20x2+ + 20x2–.

Потому что 1-ое ограничение имеет символ “≤”, то в левую часть для самостоятельной работы ограничения вводим остаточную переменную s1, а заместо переменной x2 подставляем разность: x2+ – x2–. Получим систему:

x1 + 2x2+ – 2x2– + s1 = 6,

s1 ≥ 0.

2-ое ограничение имеет символ “≥”, означает в левую часть ограничения вводим сверхизбыточную переменную s2, а заместо переменной x2, как в и прошлом ограничении, подставляем разность:

-2x1 + 7x для самостоятельной работы2+ – 7x2– – s2 = 8,

s2 ≥ 0.

Итак, каноническая форма после всех преобразований имеет вид:

max z = 13x1 – 20x2+ + 20x2– + 0s1 + 0s2 → max,

x1 + 2x2+ – 2x2– + s1 = 6,

-2x1 + 7x2+ – 7x2– – s2 = 8,

x1, x2+, x2– , s1, s2, ≥ 0.

Упражнения

1) Укажите, какая из ниже приведенных форм задач является канонической?

а) б)
в) г)
д) е)

2) Укажите, какая из ниже для самостоятельной работы приведенных задач является стандартной формой задачки линейного программирования(ЗЛП).

а) б)
в) г)


3. Главные характеристики ЗЛП

Для ЗЛП справедлива последующая аксиома.

Аксиома (о существовании решения). Если допустимое огромное количество X ЗЛП не пусто, а значение её естественно, то эта задачка имеет решение.

Определение. Огромное количество, образованное скрещением конечного числа полупространств и для самостоятельной работы гипер­плос­костей, если оно не пусто, именуется многогранным обилием.

Определение. Полиэдром именуется ограниченное многогранное огромное количество.

Огромное количество допустимых решений ЗЛП представляет собой многогранное огромное количество.

Аксиома. Пусть допустимое огромное количество X ЗЛП max cTx, x X является полиэдром. Тогда ЦФ cTx добивается собственного максимума в верхушке для самостоятельной работы X. Если функция cTx воспринимает наибольшее значение более чем в одной точке, то она добивается такого же значения в хоть какой точке, являющейся их выпуклой линейной композицией [5].

Из этой аксиомы вытекает, что огромное количество хороших точек не может быть конечным, если опти­мальная точка не единственна [9].

Алгебраическая запись ЗЛП для самостоятельной работы в канонической форме такая:

Пусть задачка (6) имеет допустимые решения и ранг матрицы A равен m (числу ограничений-равенств). Это предположение о ранге фактически не является ограничивающим. Этого можно достигнуть, исключив из системы Ax=b линейно зависимые уравнения.

Не считая того, будем считать, что n>m, т.к. случай n для самостоятельной работы=m не представляет энтузиазма, а соотношение n

Задачку (6) можно трактовать последующим образом: из всех представлений вектора b в виде линейной композиции векторов a*j, j= с неотрицательными коэффициентами избрать такое (если оно сущест­вует), коэффициенты которого для самостоятельной работы максимизируют значение функции cTx. [11]

Система ограничений ЗЛП (6) в векторной форме:

Определение. Базисом ß матрицы A именуется набор линейно-независимых столбцов: ß= .

Определение. Базовой матрицей B именуется матрица, составленная из столбцов, входящих в базис матрицы A: B .

Матрица B является невырожденной m ×m матрицей.

Определение. Базовым решением, подходящим ß, именуется вектор x Rn, в каком для самостоятельной работы:

– xj=0 при a*j ß,

– xjk есть k-я компонента вектора B–1b, где k=1,..,m.

Таким макаром, базовое решение x можно отыскать при помощи последующей процедуры:

– избрать огромное количество линейно независящих столбцов в матрице A;

– положить все составляющие вектора x, надлежащие столбцам, не входящим в базис ß, равными 0. Эти для самостоятельной работы переменные будем именовать небазисными;

– решить m приобретенных уравнений для определения оставшихся m компонент вектора x. Они будут называться базовыми переменными.

Определение. Решение x будем именовать допустимым базовым решением (ДБР), если оно является базовым и все его составляющие неотрицательны.

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

Определение. ДБР именуется невырожденным, если оно имеет точно m положительных компонент (координат). Если число положительных компонент меньше m, то решение именуется вырожденным.

Аксиома. Вектор x=(x1, x2,…, xn)T и тогда только тогда является допустимым базовым решением задачки (6), когда точка x=(x1, x2,…, xn)T является верхушкой его для самостоятельной работы многогранного огромного количества X.

Аксиома (базовая). Если ЗЛП имеет среднее решение (в ограниченной области всегда, а в неограниченной – зависимо от ограниченности мотивированной функции ), то оно совпадает, по последней мере, с одним из ДБР системы ограничений.

4. Мысль симплекс – способа

Согласно базовой аксиоме заместо исследования нескончаемого огромного количества допустимых решений, нужно изучить только конечное для самостоятельной работы число ДБР. Таким макаром, принципная схема решения ЗЛП такова[7]:

– отыскать все ДБР;

– вычислить для каждого из их соответственное значение ЦФ z;

– сопоставить и найти лучшее.

Но, в общем случае при огромных значениях n и m количество ДБР может быть большим (порядка Cnm) и практическое воплощение перебора всех ДБР станет для самостоятельной работы неосуществимым. Эти трудности обоснованы тем, что обозначенная принципная схема связана с хаотичным пе­ре­бором ДБР, без учета, как новое проверяемое ДБР изменяет ЦФ z и приближает ли оно нас к иско­мому оптимуму. Если же обозначенный перебор ДБР создавать целеустремленно, добиваясь на каждом шаге однообразного конфигурации для самостоятельной работы ЦФ z, т.е. чтоб каждое последующее ДБР было лучше предшествующего (либо, по последней мере, не ужаснее), то число анализируемых ДБР можно резко уменьшить.

Основной способ решения ЗЛП – симплекс-метод – базируется на идее поочередного улучше­ния решения. Разумеется, что для реализации этой идеи способ должен включать три главных для самостоятельной работы элемента:

– метод определения начального ДБР;

– правило перехода к последующему “наилучшему” ДБР;

– аспект, по которому можно найти оптимальность отысканного решения либо необходи­мость его предстоящего улучшения.

5. Перевоплощенная задачка

Разглядим ЗЛП в канонической форме:

Пусть нам понятно некие ДБР x системы ограничений (8). Не теряя общности, представим, что 1-ые m столбцов матрицы A для самостоятельной работы образуют базис данного ДБР.

Обозначим через B базовую матрицу для ДБР x (1-ые m столбцов матрицы A), а через N – матрицу, составленную из других столбцов матрицы A. Тогда

В согласовании с представлением (10) разобьем вектор x на подвекторы xB и xN, т.е.

где xB – вектор базовых переменных, а xN – вектор небазисных переменных.

Систему для самостоятельной работы (8) можно записать в виде:

Потому что матрица B – невырожденная, то она имеет оборотную матрицу B–1 тогда

Система (12) эквивалентна системе (11).

Сейчас разобьем вектор c на подвекторы cB и cN, в согласовании с разбиением (10) матрицы A.

Тогда задачку (7)–(9) можно записать в виде:

Подставим значение xB в ЦФ задачки:

Тогда для самостоятельной работы начальная задачка может быть представлена в виде:

Получили так именуемую перевоплощенную задачку. Обозначив

можно записать перевоплощенную задачку последующим образом:

Потому что xN=0, то xB воспринимает числовое значение β, а ЦФ – значение cBTβ. Но, в перевоплощенную задачку врубаются все члены правых частей уравнений (не глядя на то, что xN=0), т.к. они указывают на то для самостоятельной работы, что произойдет с ЦФ и xB, если один из частей вектора xN возрастает, начиная с нуля.

Время от времени задачку (13)-(15) именуют диагональной формой начальной задачки, соответственной ДБР x, а система (14) именуется диагональной системой относительно переменных x1,x2,…,xm. Система названа диагональной, так как представима в виде:

Разумеется для самостоятельной работы, что наше ДБР .

6. Метод перехода от 1-го ДБР к другому

Пусть ДБР x0 соответствует перевоплощенной задачке (13)-(15). Перейдем от него к новенькому ДБР x1. При всем этом разглядим возможность того, что только одна небазисная переменная станет возрастать, принимая по­ложительные значения, в то время как другие небазисные переменные останутся нулевыми [10]. Обозначим

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

.

Пусть начиная с нуля, увеличивается переменная (xN)p, означает, вектор базовых переменных меняется согласно уравнению

потому что другие небазисные переменные остаются равными нулю. При всем этом, зависимо от значений ком­понент вектора a
*p вероятны 3 последующих варианта:

– если ая компонента вектора равна нулю ( ), то для самостоятельной работы соответственный ей элемент вектора остается без конфигураций;

– если ая компонента вектора отрицательна ( ), то соответственный ей элемент будет возрастать;

– если ая компонента вектора положительна ( ) – соответственный ей элемент будет уменьшаться и станет меньше нуля, когда величина (xN)p сделается довольно большой. Этого допустить нельзя, т.к. будет нарушена допустимость x для самостоятельной работы1.

Отсюда получаем очень допустимое повышение значения (xN)p

где aip и βi – элементы векторов a*p и β соответственно.

Пусть минимум в этом уравнении достигается при i=q тогда, если , то в новеньком ДБР имеем:

Отметим, что выбор q однозначен. Если уже выбрана увеличиваемая небазисная переменная p-я, то базовая q-я для самостоятельной работы, которая 1-ая обратится в нуль, определяется величинами a*p и β. Если в нуль обращаются сразу две либо более базовых переменных, мы имеем дело с вырожденным случаем, но избрать мы должны только одну из их.

Итак, мы пришли к последующей ситуации: переменная (xN)p стала базовой со значением для самостоятельной работы , а переменная (xB)q – небазисной (со значением 0). Это значит такую перестановку в разбиении матрицы A, что столбец a*p становится на место q-го столбца матрицы B. В данном случае будем гласить, что (xN)p «вводится» в базис, а (xN)p «выводится» из него.

Описанный метод перехода от 1-го для самостоятельной работы ДБР к другому именуется операцией замещения.

7. Условие оптимальности ДБР

Определение.Вектор-строка, на которую множится слева xN в уравнении для ЦФ (13), именуется век­тором относительных оценок, т.к. он показывает, в какую сторону и как поменяется ЦФ при изменении xN.

Обозначим этот вектор через dN. Его j-ый элемент определяется для самостоятельной работы так:

Если относительная оценка (dN)j, то небазисной переменной (xN)j положительна либо равна нулю, но значение ЦФ не возрастает при увеличении (xN)j, начиная с нуля [11].

Аксиома (условие оптимальности).Для ДБР x0 операция замещения, при которой (xN)p вводится в базис, изменяет значение ЦФ на величину

где

Если dN≥0, то x0 нормально для самостоятельной работы.

ЗЛП будем именовать невырожденной, если все ее ДБР не вырождены. Справедлива аксиома, оборотная последней аксиоме.

Аксиома. Пусть ЗЛП является невырожденной, а x0 – ДБР, являющееся ее решением. Тогда dN≥0.

В этом случае, если ЗЛП не является невырожденной, предшествующая аксиома приобретает вид:

Аксиома. Для того, чтоб ДБР x0 являлось для самостоятельной работы решением начальной ЗЛП, нужно и довольно су­ществование такового базиса для x0, для которого dN≥0.

Аксиома. Если некому ДБР начальной задачки соответствует задачка, для которой существует не­базисная переменная (xN)p такая, что (dN)p<0 и (aN)*p≤0, то мотивированная функция начальной задачки не ограни­чена на огромном количестве допустимых для самостоятельной работы решений (θ не ограничено сверху и можно сколько угодно наращивать мотивированную функцию).

Пример 7.1

Дана ЗЛП

.

Знайти всі компоненти перетвореної задачі для ДБР, який відповідає базису . Чи є оптимальним цей ДБР?

Розв’язок

Базисні, небазисні змінні та відповідні їм векторикоєфіцієнтів ЦФ:

.

Небазисна матриця та вектор правих частин обмежень:

.

Базисна матриця та матриця, обернена до неї:

.

Значення для самостоятельной работы базисних змінних та ЦФ:

Вектор відносних оцінок небазисних змінних:

Оскільки вектор відносних оцінок небазисних змінних містить додатні компоненти, а задачка на максимум, то поточний базисний розв'язок не є оптимальним.

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

Рассмотренные в разделах 6-7 методы перехода от 1-го ДБР к другому и аксиомы ЛП, позволяют выстроить для самостоятельной работы так именуемый симплекс-метод решения ЗЛП в канонической форме, который имеет сле­дующую схему:

Шаг 0. Построение исходного ЗЛП.

Пусть задано ДБР x0 начальной ЗЛП (такое ДБР именуется исходным). Пусть данному ДБР соот­ветствует базис ß, вектор базовых переменных xB=B–1β, небазисных переменных xN, базовая матрица B, небазисная матрица N.

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

Шаг 2. Проверка выполнения условия оптимальности.

Если производится dN≥0, то закончить вычисления – текущее ДБР является решением начальной задачки. По другому – перейти на шаг 3.

Шаг 3. Выбор небазисной переменной (xN)p, вводимой во огромное количество базовых переменных.

Избрать p, для которого (dN)p<0 (обычно p соответствует наибольшая по для самостоятельной работы модулю отрицательная компонента dN).

Шаг 4. Выбор базовой переменной, выводимой из огромного количества базовых переменных.

Вычислить a*p=B–1a*p (пересчет столбца вводимого в базис).

Если a*p<0, то закончить вычисления – мотивированная функция не ограничена сверху.

Избрать q, для которого производится , т.е. переменная (xB)q будет для самостоятельной работы выведена из огромного количества базовых переменных.

Шаг 5. Операция замещения.

Выстроить базис нового ДБР методом подмены q-го столбца a*p текущего базиса ß на столбец a*p. Выстроить новые базовую матрицу B и небазисную матрицу N. Отыскать новые значения базовых переменных xB=B–1b и ЦФ cBTβ.

Перейти на шаг1.

Пример 4

Дана система для самостоятельной работы ограничений:

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

– ,

– ,

– . ?

если да , то какие решения им соответствуют:

Решение. Базисом β матрицы А именуется набор из линейно-независимых столбцов β= .

Решение именуется допустимым базовым решением если оно является базовым и все его составляющие не отрицательны.

В нашей задачке m=3, n=5. Другими словами для самостоятельной работы количество претендентов на базис в нашей задачке будет менее, чем .

а) Разглядим 1-ое огромное количество векторов - . Составим матрицу из этих векторов, если её детерминант будет отличен от нуля, то эти векторы составляют базис:

.

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

Соответственное базовое решение имеет вид:

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

b) Разглядим огромное количество векторов - .

Сейчас составим матрицу из соответственных векторов и найдём её определителю:

Означает огромное количество векторов является базисом. Найдём соответственное ему базовое решение, для этого выпишем уравнения системы с учетом того, что :

Итак для самостоятельной работы, данному базису соответствует решение:

базовые переменные
небазисная переменная
базовая переменная
небазисная

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

с) Разглядим огромное количество векторов - .

Составим матрицу из этих векторов,

Означает для самостоятельной работы огромное количество векторов является базисом.

Выпишем уравнения системы с учетом того, что :

Таким макаром, соответственное базовое решение таково:

- небазисые переменные
- базовые переменные
- базовая переменная

Итак, базису соответствует решение, у которого одна переменная отрицательна, как следует, имеем недопустимое базовое решение.

9. Табличный симплекс-метод

Пусть для начальной ЗЛП задано изначальное ДБР, базис которого образуют 1-ые для самостоятельной работы m столбцов матри­цы A. Введем новейшую переменную z и при помощи простых преобразований Жордана-Гаусса преобразуем расширенную систему к диагональной форме относительно переменных z, x1, x2,…, xm:

,

,

Диагональная форма (19) начальной системы ограничений, приобретенная с помощью преобразований Жордана-Гаусса, совпадает с диагональной формой (13)-(15), приобретенной матричным методом.

Диагональной форме (19) можно для самостоятельной работы поставить в соответствие последующую таблицу, которая получила заглавие симплекс-таблицы:

Таблица 1

БП z x1 xm xm+1 xn Решение
z b0
x1 a1,m+1 a1,n b1
xm am,m+1 am,n bm

В левом столбце таблицы перечислены базовые переменные. В общем случае в этом столбце таблицы в для самостоятельной работы i-ой строке будет записана переменная (xB)i.

Слева от таблицы указаны базовые переменные.

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

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

На самом деле, симплекс-метод и табличный симплекс-метод соотносятся меж собой как способ и метод.

В предстоящем столбец будем опускать, потому что от итерации к итерации он не меняется .

9.1. Схема табличного симплекс-метода

Шаг 0. Исходный шаг

Выстроить изначальное ДБР начальной задачки.

Выстроить подобающую этому ДБР симплекс для самостоятельной работы-таблицу.

Шaг 1. Проверка условия оптимальности

ЕСЛИ коэффициенты z-строки

неотрицательны - в случае задачки на максимум

(неположительны - в случае задачки на минимум),

ТО закончить вычисления: текущей симплекс-таблице соответствует наилучшее ДБР.

Шаг 2. Выбор переменной, вводимой в базис.

Посреди коэффициентов избрать отрицательный.

Пусть мы избрали .

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

Шаг 3. Выбор переменной, выводимой из базиса

ЕСЛИ все коэффициенты ведущего столбца неположительные, то закончить вычисления: мотивированная функция не ограничена сверху.

По другому избрать переменную , которой соответствует минимум в выражении

.

-ая строчка именуется ведущей.

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


dlya-nego-schaste-bilo-plodom-vnutrennego-pokoya.html
dlya-nih-net-chuzhoj-boli-otkrit-vtoroj-vek-otechestvennoj-animacii-priehali-vo-vladimirskuyu-oblast-avtori-sotni.html
dlya-normalnogo-razvitiya-i-funkcionirovaniya-organizma-sohraneniya-zdorovya-neobhodim-opredelennij-uroven-fiz-aktivnosti.html