Искусственное начальное решение. Метод больших штрафов
В задаче 1 для получения начального базисного решения использовались остаточные переменные. Однако, когда исходное ограничение записано в виде равенства или имеет знак 
, нельзя сразу же получить допустимое начальное базисное решение. Покажем это на конкретном примере.
Начальная форма задачи: Стандартная форма задачи:
Таким образом, имеются три уравнения, содержащие четыре неизвестных. Это означает, что каждому базисному решению соответствует одна небазисная переменная (равная нулю). В отличие от случая, когда каждое уравнение содержит остаточную переменную, в данной ситуации уже нельзя быть уверенным в том, что при нулевом значении одной из переменных все базисные переменные будут неотрицательными. При выборе переменной, которой следует приписать нулевое значение, можно, конечно, использовать метод проб и ошибок. Однако этот метод требует дополнительных затрат времени и неудобен для выполнения расчетов. Поэтому следует применить более рациональный способ нахождения начального допустимого базисного решения.
Идея использования искусственных переменных достаточна проста. Она предполагает включение неотрицательных переменных в левую часть каждого из уравнений, не содержащих «очевидных» начальных базисных переменных. Обеспечивая получение начального базиса, эти дополнительно вводимые переменные выполняют, по существу, ту же роль, что и остаточные переменные. Однако, поскольку такие искусственные переменные не имеют отношения к содержанию поставленной задачи, их введение допустимо только в том случае, если соответствующая схема вычислений будет обеспечивать получение оптимального решения, в котором все искусственные переменные окажутся равными нулю.
Для построения требуемой схемы вычислений можно применить следующий прием: наложить «штраф» за использование искусственных переменных, вводимых в целевую функцию. Разработаны два метода получения стартовой точки, в которых используется «штрафование» искусственных переменных: метод больших штрафов и двухэтапный метод.
Рассмотрим схему применения метода больших штрафов в нашем примере. В первом и втором уравнениях нет переменных, выполняющих роль остаточных. Поэтому введём в каждое из этих уравнений по одной искусственной переменной, обозначив их через 
и 
:
За использование этих переменных в составе целевой функции можно ввести штраф, приписывая им достаточно большой положительный коэффициент 
. Такой способ введения искусственных переменных приводит к следующей линейной модели:
| Базис | с | 
| -4 | -1 | -М | -М | 
| Замечания | ||
| 
| 
| 
| 
| 
| |||||
|
| ||||||||||
|
| -М | 1 - min | ||||||||
|
| -М | -1 | 
| |||||||
| -9М | -7М+4 | -4М+1 | М | |||||||
|
| 
| Z | 
| Т.к. искусственная переменная из базиса исключена, то соответствующий столбец можно уже не заполнять.
| ||||||
|
| -4 | 
| ||||||||
|
| -М |
| -1 |  -min
| ||||||
| -2M-4 | - M-
| M | ||||||||
|
| Z | Z | 1-min | |||||||
|
| -4 | 
| 
| |||||||
|
| -1 |
| -
| отриц. | ||||||
- 
| -
| |||||||||
|
| Z | Z |  ;
| |||||||
|
| -4 | 
| -
| |||||||
|
| -1 |
|
| |||||||
- 
|
|