Цель: научиться аналитически решать задачу линейного программирования; сопоставлять полученные графическое а аналитическое решения.  
## Алгоритм решения задачи симплексным методом
**Шаг 1. Найти начальное базисное решение**
Записать исходную задачу в канонической форме. За начальные базисные переменные берутся те m переменных, при которых коэффициенты в уравнениях ограничений образуют единичную матрицу. Этого можно добиться, осуществляя преобразования Гаусса-Жордана. Вторым способом нахождения базисного решения является переход к M-задаче.  
Выделить базисные и свободные (все остальные, кроме базисных) переменные.  
Найти начальное базисное решение, полагая свободные переменные равными нулю.  
**Шаг 2. Заполнить таблицу**

|          |      |      | $c_1$               | $c_2$               | ... | $-M$       | $c_j$                  |
| -------- | ---- | ---- | ------------------- | ------------------- | --- | ---------- | ---------------------- |
| $c_{iB}$ | $БП$ | $БР$ | $x_1$               | $x_2$               | ... | $x_{n+_m}$ | $БР/\overline{a_{ir}}$ |
|          |      |      | $\overline{a_{11}}$ | $\overline{a_{12}}$ |     | 0          |                        |
|          |      |      | ...                 | ...                 |     |            |                        |
|          |      |      | $\overline{a_{m1}}$ | $\overline{a_{m2}}$ |     | 1          |                        |
|          |      |      | $z_1$               | $z_2$               |     | $z_{n+m}$  | $z_j$                  |
|          |      |      | $Δ_1$               | $Δ_2$               |     | $Δ_{n+m}$  | $Δ_j$                  |
  
- $БП$ – столбец базисных переменных;
- $БР$ – столбец базисного решения;
- $c_j$ – строка коэффициентов целевой функции;
- $c_{iB}$ – столбец коэффициентов целевой функции, соответствующих базисным перменным;
- $𝑎_{𝑖𝑗}$ – коэффициенты системы ограничений задачи ЛП после выполнения преобразований, предусмотренных Шагом 1.
  
**Шаг 3. Вычислить относительные оценки, записать их в таблицу**  
- $Δ_j=c_j-\sum{^m_{i=1}}c_{iB}\overline{a}_{ij}=c_j-z_j$
- $z_j=\sum{^m_{i=1}}c_{iB}\overline{a}_{ij}$
- $j=1,...,m+n$
  
**Шаг 4. Проанализировать относительные оценки (задача была записана в канонической форме, следовательно, предполагается поиск максимума):**
- если все оценки $Δ_j$ неположительны, то расчет закончен. Найденное базисное решение является оптимальным;
- если есть положительные оценки, то следует найти максимальную среди них и проанализировать коэффициенты столбца таблицы, которому соответствует максимальная положительная оценка. Если этот столбец содержит хотя бы один положительный коэффициент, то номер столбца обозначается через $r$, а переменная, соответствующая ему, вводится в число базисных. Если среди коэффициентов этого столбца нет ни одного положительного, то это означает, что множество допустимых решений задачи не ограничено, а функция $f(x)$ не ограничена сверху и задача решения не имеет.
  
Столбец, соответствующий выбранной оценке, называется разрешающим.  
**Шаг 5. Поделить элементы столбца базисных решений (БР) на соответствующие элементы разрешающего столбца и среди полученных частных выбрать наименьшее.**  
Строка, соответствующая выбранному отношению, называется разрешающей.  
Из числа базисных выводится переменная, соответствующая разрешающей строке, а на ее место вводится переменная, соответствующая базисному столбцу.  
Таким образом, новая переменная $x_r$ вводится на место переменной $x_{sB}$, удаляемой из базиса.  
Элемент, лежащий на пересечении разрешающего столбца и разрешающей строки, называется разрешающим ($\overline{𝑎}_{𝑠𝑟}$).  
**Шаг 6. Вычислить новое базисное решение, выполнив перерасчет таблицы:**  
каждый элемент разрешающей строки существующей таблицы делится на разрешающий элемент и записывается в новую таблицу;  
все остальные элементы находятся по правилу прямоугольника: $a_{ij}=\overline{a}_{ij}-\frac{\overline{a}_{sj}\overline{a}_{ir}}{\overline{a}_{sr}}$  
![Правило многоугольника](../../Pictures/ЛБ02_01.%20Правило%20многоугольника.png)  
Перейти к шагу 3.
## Переход к М-задаче
В том случае, если в уравнениях ограничений канонической задачи нет базисных переменных, то для того, чтобы применить симплексный метод, нужно сделать переход к M-задаче. В каждое из m уравнений вводится искусственная переменная со знаком «+», которая становится базисной. К целевой функции добавляется сумма искусственных переменных, умноженная на «-M». В результате получаем задачу в расширенной форме:  
$$f(x)=\sum{^n_{j=1}}c_jx_j-M\sum{^m_{i=1}x_{n+p+i}\rightarrow max}$$$$\sum{^n_{j=1}}a_{ij}x_j-x_{n+i}+x_{n+p+i}=b_i, i=1,...,m$$
$$\sum{^n_{j=1}}a_{ij}x_j+x_{n+i}=b_i, i=m+1,...,p$$
$$x≥0,...,x_{n+p+m}≥0$$
Если решается задача поиска минимума целевой функции, то при переходе к M-задаче перед числом M ставится знак «+».
## Задание на лабораторную работу
Решить задачу линейного программирования, соответствующую варианту симплексным методом. проиллюстрировать решение графически (если можно).  
При решении задачи могут быть использованы любые пакеты прикладных программ, но при этом в отчете должны быть представлены:
- базисное решение,
- симплексные таблицы,
- оптимальное решение,
- графическая иллюстрация,
- ответы на контрольные вопросы
  
Сопоставить свое решение с тем, что предлагает Excel
#### Вариант 4
$f(x)=x_1-2x_2+2x_3-x_4\rightarrow extr$  
$x_1+x_3-3x_4=3$  
$2x_1+x_2+x_4=7$  
$x_1,x_2,x_3,x_4≥0$  
## Контрольные вопросы
1. Приведите общую постановку задачи и каноническую. Каким образом можно перейти от общей постановки задачи к канонической?
2. Какие переменные называются базисными, а какие свободными? Какие способы нахождения начального базисного решения существуют?
3. На основании каких признаков можно сделать вывод о:
4. количестве решений задачи линейного программирования;
5. совместна или нет система ограничений.
6. Чем отличается решение задачи о поиске минимума от решения задачи о поиске максимума?