Табличный алгоритм обмена переменных

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

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

1. Меняются местами заголовки разрешающей строки и разрешающего столбца .

2. Разрешающий элемент заменяется на обратную ему величину .

3. Все элементы разрешающего столбца (кроме самого разрешающего элемента) меняют знак и умножаются на новый разрешающий элемент:

.

4. Каждый из элементов, кроме принадлежащих разрешающей строке или разрешающему столбцу, подвергаются следующему преобразованию: к нему прибавляется произведение элемента, стоящего в разрешающей строке (пока это старое значение) на том же месте по порядку (т.е. в том же столбце), на элемент стоящий в новом разрешающем столбце на соответствующем месте (т.е. в той же строке, что и наш элемент):

5. Все элементы разрешающей строки (кроме разрешающего) умножаются на новый разрешающий элемент:

Отыскание опорного решения озлп

1. Если все свободные члены (не считая строки ) в симплекс-таблице неотрицательны, опорное решение получено.

2. Если в столбце свободных членов есть отрицательный элемент, а в строке, соответствующей ему, нет ни одного отрицательного элемента, то опорного (и вообще допустимого) решения не существует.

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

Поиск оптимального решенияОзлп

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

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

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

Порядок работы

1. Записать систему уравнений, соответствующую полученному варианту заданий в виде , . Дать описание всем введённым переменным.

2. Ввести добавочные переменные и представить систему в виде уравнений , .

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

4. Выполнить контрольную проверку решения с использованием программы Excel.

5. Составить алгоритм симплекс-метода и реализовать его на языке Pascal (выбор другого языка программирования с разрешения преподавателя).

6. Найти решение задачи с использованием Вашей программы и сравнить его с полученными ранее (п.п. 3, 4).