Описание проекта
И сказал Бог: "Да будет Примат".....
Первая лаба - важнейшая в каждом семестре! И особенно, если это первая лаба по Примату! Именно поэтому мы решили подойти к первой лабораторной работе по Примату в формате группового проекта для Devtools. Суть лабораторной заключается в реализации симплекс-метода на Python для решения задач линейного программирования.
Что такое задача линейного программирования?
Очень просто! Рассмотрим простейшую задачу линейного программирования на примере:
Суть задачи чрезвычайно проста - нам нужно максимализировать прибыль. Переводя на язык математики - найти максимум функции C.
Именно это и является типичным примером задачи линейного программирования.
Что такое симплекс-метод?
Симплекс метод - это метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).
По-человечески - это способ решения задач линейного программирования через последовательное составление симплекс-таблиц до тех пор, пока в симплекс-таблице не окажется оптимального решения.
Алгоритм симплекс-метода:
Шаг 1. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на - 1) и в каждое ограничение ввести дополнительные переменные (со знаком "плюс", если в исходном неравенстве знак "меньше или равно", и со знаком "минус", если "больше или равно").
Шаг 2. Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
Шаг 3. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным - решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
Шаг 4. Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.
Пример решения задачи симплекс-методом
Это было сделано с соблюдением следующего правила: если в первоначальном ограничении знак "меньше или равно", то добавочную переменную нужно прибавлять, а если "больше или равно", то добавочную переменную нужно отнимать.
Выразив основные (базисные) переменные через неосновные (свободные), получим
Функцию цели также выразим через неосновные (свободные) переменные:
Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.
Последнюю строку таблицы, в которой записаны функция цели и коэффициенты при свободных переменных в ней, будем называть в индексной строкой.
Полученное решение не оптимально, так как в индексной строке коэффициенты при свободных переменных отрицательны. То есть оптимальным будет то решение, в котором коэффициенты при свободных переменных в индексной строке будут больше или равны нулю.
Для определения ведущей строки находим минимум отношений свободных членов к элементам ведущего столбца, причём если в числителе положительное число, а в знаменателе отрицательное, отношение считается равным бесконечности.
Итак,
Ведущим элементом, таким образом, является -2.
Составляем вторую симплексную таблицу.
Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).
Заполняем столбец вспомогательных коэффициентов. Для этого числа ведущего столбца таблицы 1, кроме ведущего элемента, записываем с противоположными знаками в графу вспомогательных коэффициентов таблицы 2.
Таким образом мы проделываем данные операции до тех пор, пока не получим положительные свободные неизвестные в индексной строке. В нашем случае мы получили такую таблицу на 5-ой итерации:
Смотрим в симплексную таблицу 5. Видим, что получено оптимальное решение, так как коэффициенты при свободных неизвестных в индексной строке неотрицательны.
Ответ:
Last updated