40. Способы перехода от одной формы задачи лп к другой.

41. Базисное решение задачи лп.

Таким образом, базисом называют любой набор из m переменных, для которых определитель, составленный из коэффициентов при этих переменных, не равен нулю.

Полученное при этом решение называют базисным, а переменные, которые были приравнены к нулю называются свободными.

+Эти m переменных называют базисными. Остальные n переменных называют свободными. (Свободные переменные = 0)

Т. о., если приравнять все свободные переменные нулю, то можно решить полученную систему из m уравнений с m неизвестными. Полученное при этом решение называют базисным.

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

43 Графический метод решения задачи лп.

44. Симплекс-метод решения задачи лп.

Формализованный алгоритм симплекс метода состоит из двух основных этапов [8]: 1) построение опорного плана; 2) построение оптимального плана.

Построение оптимального плана. Для того чтобы опорный план был оптимален при минимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неположительными (в случае максимизации – неотрицательными). То есть, при поиске минимума мы должны освободиться от положительных коэффициентов в строке Q x . Выбор разрешающего элемента. Если при поиске минимума в строке целевой функции есть коэффициенты больше нуля, то выбираем столбец с положительным коэффициентом в строке целевой функции в качестве разрешающего. Пусть это столбец с номером l . Для выбора разрешающей строки (разрешающего элемента) среди положительных коэффициентов разрешающего столбца выбираем тот (ту строку), для которого отношение коэффициента в столбце свободных членов к коэффициенту в разрешающем столбце минимально:        min il  0 il i rl r a a b a b . Тогда rl a – разрешающий (направляющий) элемент, строка r – разрешающая. Для перехода к следующей симплексной таблице (следующему опорному плану с меньшим значением целевой функции) делается шаг модифицированного жорданова исключения с разрешающим элементом rl a . Если в разрешающем столбце нет положительных коэффициентов, то целевая функция неограничена снизу (при максимизации – неограничена сверху).

45. Метод Искусственных переменных

Задачи ЛП с использованием СМ легко решаются лишь при ограничениях типа <. При ограничениях-равенствах или ограничениях типа >, когда имеют дело с остаточными переменными, возникают трудности, связанные с получением начального допустимого базисного решения.

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

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

С применением искусственных переменных связаны два основных метода: метод больших штрафов (М-метод) и двухэтапный метод.

Метод больших штрафов. В этом методе в задачу ЛП вводится обратная связь, которая обеспечивает получение оптимального решения при нулевых искусственных переменных. В качестве такой обратной связи используется штраф, накладываемый на ЦФ за использование искусственных переменных.

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

На первом этапе вводятся искусственные переменные, необходимые для получения стартовой точки; формируется фиктивная ЦФ (р как сумма искусственных переменных, выраженных из соответствующих ограничений. Решается задача минимизации функции ф. Если минимальное значение функции Ф равно нулю, то исходная задача имеет допустимое решение, в противном случае задача решения не имеет. Основная цель первого этапа — получение начального решения исходной задачи.

На втором этапе решается исходная задача, при этом в качестве начального решения используется оптимальное решение, полученное на первом этапе.