> For the complete documentation index, see [llms.txt](https://primat-lab-1.gitbook.io/lab1-outer-doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://primat-lab-1.gitbook.io/lab1-outer-doc/opisanie-proekta.md).

# Описание проекта

Первая лаба - важнейшая в каждом семестре! И особенно, если это первая лаба по Примату! Именно поэтому мы решили подойти к первой лабораторной работе по Примату в формате группового проекта для Devtools.\
Суть лабораторной заключается в реализации симплекс-метода на Python для решения задач линейного программирования.

### Что такое задача линейного программирования?

Очень просто!\
Рассмотрим простейшую задачу линейного программирования на примере:

**Задача.** Для изготовления столов и шкафов используется два вида древесины: ![](https://function-x.ru/linprog/lp031.gif) и ![](https://function-x.ru/linprog/lp032.gif). Для изготовления одного шкафа используется ![](https://function-x.ru/linprog/lp033.gif) древесины ![](https://function-x.ru/linprog/lp031.gif) и ![](https://function-x.ru/linprog/lp034.gif) древесины ![](https://function-x.ru/linprog/lp032.gif). Для изготовления одного стола используется ![](https://function-x.ru/linprog/lp035.gif) древесины ![](https://function-x.ru/linprog/lp031.gif) и ![](https://function-x.ru/linprog/lp033.gif) древесины ![](https://function-x.ru/linprog/lp032.gif). Доход мастерской от производства одного стола составляет 12 у. е., от производства одного шкафа - 15 у. е. Определить, сколько столов и сколько шкафов должна изготовить мастерская, чтобы обеспечить наибольшую рентабельность их производства, если в распоряжении мастерской имеется древесины ![](https://function-x.ru/linprog/lp031.gif) ![](https://function-x.ru/linprog/lp036.gif), а древесины ![](https://function-x.ru/linprog/lp032.gif) ![](https://function-x.ru/linprog/lp037.gif).

Представим данные в виде таблицы:\
![](/files/1BApLSjMoIQBnRrsTPFH)

Количество столов обозначим через ![](https://function-x.ru/linprog/lp021.gif), количество шкафов - ![](https://function-x.ru/linprog/lp022.gif). Тогда из таблицы легко составить систему ограничений ![](https://function-x.ru/linprog/lp038.gif):

![](https://function-x.ru/linprog/lp040.gif)

и функцию цели ![](https://function-x.ru/linprog/lp039.gif):

![](https://function-x.ru/linprog/lp041.gif).

Суть задачи чрезвычайно проста - нам нужно максимализировать прибыль. Переводя на язык математики - найти максимум функции C. 

Именно это и является типичным примером задачи линейного программирования.

### Что такое симплекс-метод?

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

***По-человечески*** - это способ решения задач линейного программирования через последовательное составление симплекс-таблиц до тех пор, пока в симплекс-таблице не окажется оптимального решения. 

#### Алгоритм симплекс-метода:

* **Шаг 1**. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на - 1) и в каждое ограничение ввести дополнительные переменные (со знаком "плюс", если в исходном неравенстве знак "меньше или равно", и со знаком "минус", если "больше или равно").
* **Шаг 2**. Если в полученной системе *m* уравнений, то *m* переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
* **Шаг 3**. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
* **Шаг 4**. Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.

### **Пример решения задачи симплекс-методом**

Пример**:** Найти максимум функции ![](https://function-x.ru/linprog/sm002.gif) при ограничениях

![](https://function-x.ru/linprog/sm003.gif)

![](https://function-x.ru/linprog/sm004.gif)

 Вводим добавочные неотрицательные переменные ![](https://function-x.ru/linprog/sm005.gif) и сводим данную систему неравенств к эквивалентной ей системе уравнений

![](https://function-x.ru/linprog/sm006.gif)

![](https://function-x.ru/linprog/sm007.gif).

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

Введённые добавочные переменные принимаем за основные (базисные). Тогда ![](https://function-x.ru/linprog/sm008.gif) и ![](https://function-x.ru/linprog/sm009.gif) - неосновные (свободные) переменные.

Выразив основные (базисные) переменные через неосновные (свободные), получим

![](https://function-x.ru/linprog/sm075.gif)

Функцию цели также выразим через неосновные (свободные) переменные:

![](https://function-x.ru/linprog/sm076.gif)

Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.

![](/files/3x86lpXax8jRr7yb6rXS)

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

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

Для перехода к следующей таблице найдём наибольшее (по модулю) из чисел ![](https://function-x.ru/linprog/sm077.gif) и ![](https://function-x.ru/linprog/sm078.gif). Это число 2. Поэтому ведущий столбец - тот столбец, в котором записано ![](https://function-x.ru/linprog/sm079.gif)

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

Итак,

![](https://function-x.ru/linprog/sm080.gif).

Поэтому ведущая строка - та, в которой записано ![](https://function-x.ru/linprog/sm081.gif)

Ведущим элементом, таким образом, является -2.

Составляем вторую симплексную таблицу.

Новый базисный элемент ![](https://function-x.ru/linprog/sm079.gif) вписываем первой строкой, а столбец, в котором стояло ![](https://function-x.ru/linprog/sm079.gif), вписываем новую свободную переменную ![](https://function-x.ru/linprog/sm081.gif)

Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).

Заполняем столбец вспомогательных коэффициентов. Для этого числа ведущего столбца таблицы 1, кроме ведущего элемента, записываем с противоположными знаками в графу вспомогательных коэффициентов таблицы 2.

![](/files/goTbz4TAuHiVsPKxkyXK)

Таким образом мы проделываем данные операции до тех пор, пока не получим положительные свободные неизвестные в индексной строке. В нашем случае мы получили такую таблицу на 5-ой итерации:

![](/files/nzFKZ5U9l2gV1MeX36sv)

Смотрим в симплексную таблицу 5. Видим, что получено оптимальное решение, так как коэффициенты при свободных неизвестных в индексной строке неотрицательны.

Ответ:

![](https://function-x.ru/linprog/sm109.gif)