Метод получения начальных точек

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

       x₁           +a_1m+1x_m+1+...a_1nx_n=b₁'

            x₂      +a_2m+1x_m+1+...a_2nx_n=b₂'        (*)

.                   .   .          ..      .

                x_m +a_mm+1x_m+1+   a_mnx_n=b_m'

Умножаем уравнения на коэффициенты c_n и складываем, затем вычитаем из них  уравнение

Z=c₁x₁+c₂x₂+....c_nx_n

 в результате x₁,x₂,....   x_m исключаются из Z  и мы получаем

c_m+1x_m+1+c_m+2x_m+2+...c_nx_n=z-z_0,              (**)

где Z₀=S_i^m₌₁c_ib_i

Форма (*) и(**) называется канонической

При x_m+1,.....   x_n=0 получаем

x₁=b₁,x₂=b₂,....x_m=b_m, x_m+1,...x_n - начальное решение. Если все b_i  положительны, то это решение допустимое. Симплекс метод обеспечивает систематическую процедуру для замены одной допустимой формы другой, при которой значение целевой функции уменьшается. Этот итерационный процесс удобно проводить с помощью т.н. симплекс -таблиц. Коэффициенты в канонической форме и начальное базисное решение записывается в виде симплекс-таблицы

Итерационный процесс решения состоит из трех шагов:

1)Поиск переменной для включения в базис

2)поиск переменной для исключения из базиса

3)построение новой канонической формы.

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

1)число ограничений, число переменных

        (2)                   (4)

2)коэффициенты при переменных при ограничениях

       3,4,1,0

       2,5,0,1

4)коэффициенты в линейной форме при переменных

   -2,-4,0,0

5)начальное значение коэффициента В и линейной формы

6)номера( индексы) небазисных переменных, т.е.которые вводим

    3,4

Различные программы симплекс приведены в книгах /3,10/.