Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
Аннотация к работе
В данном курсовом проекте были изучены теоретические основы задач линейного программирования, история происхождения универсального метода последовательного улучшения решения, теоретические сведения о применении разновидностей симплекс-метода в жизни. Для упрощения нахождения оптимального плана (решения) был написан модуль, реализующий работу симплексного метода. Роль симплексного метода достаточно велика, т.к. симплекс-метод находит применение для решения широкого круга задач линейного программирования в экономической сфере, сфере планирования и других сферах, связанных с производством, и до настоящего времени является одним из основных методов.
Введение
симплекс линейный программирование алгебраический
Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены.
Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глаз» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием.
Существует большое число разнообразных по содержанию задач линейного программирования, сводящихся к нахождению максимума (минимума) линейной функции, заданной на многограннике, и имеющих аналогичный математический характер. Например, это могут быть задачи планирования, выбора загрузки оборудования, управления запасами, задачи распределения ресурсов, распределения транспортных грузопотоков и т.д. Максимум (минимум) таких функций достигается в вершине, однако число вершин может достигать миллиарда и простой перебор вершин не годится. Поэтому и возникает необходимость изучения методов решения или нахождения оптимального плана задач линейного программирования.
Исходя из вышесказанного, следует актуальность темы курсового проекта.
Предметом исследования курсового проекта являются разновидности решения симплексного метода.
Объектом является процесс нахождения оптимального или эффективного решения (плана) задач линейного программирования.
Цель данного курсового проекта - научиться находить оптимальное решение в экономических задачах линейного программирования.
Задачи курсового проекта: u изучить теоретические основы задач линейного программирования;
u рассмотреть работу симплексного метода и его разновидностей;
u применить разновидности симплексного метода к решению прикладных задач;
u написать программный модуль, реализующий работу симплекс-метода.
1. Линейное программирование. Симплексный метод
1.1 Линейное программирование
Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л.В. Канторовичу. Год спустя, в 1939 г., Л.В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов. Дж. Данциг разработал математический аппарат симплексного метода решения задач линейного программирования (1951 г.). Симплексный метод находит применение для решения широкого круга задач линейного программирования и до настоящего времени является одним из основных методов.
Линейное программирование (ЛП) - это раздел математики, ориентированный на нахождение экстремума (максимума или минимума) в задачах, которые описываются линейными уравнениями. Причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (переменные) условия ограничений на входные параметры.
Целевая функция (критерий задачи или критерий эффективности) - результат принятого решения, который описывается функцией. Аргументами целевой функции (F(x)) являются разные варианты решений, а значениями - числа.
Математическая модель - система математических соотношений, приближенно в абстрактной форме описывающих изучаемый процесс.
Каждая модель служит для достижения следующих целей: 1) познавание объекта или процесса;
2) прогнозирование поведения объекта;
3) принятие наилучших решений.
Этапы построения математической модели: 1. Определение параметров модели (?) - фиксированные данные, на значения которых исследователь не влияет.
2. Формирование управляющих переменных (xi). Изменяя их значения, получаем оптимальное решение.
3. Определение области допустимых решений (Х) - ОДР. Это ограничения на управляющие переменные.
4. Выявление неизвестных факторов (?). Эти факторы изменяются случайным образом и не могут изменяться исследователем.
5. Задание целевой функции (F). В общем виде целевая функция записывается F (?, xi, ?) > max (min).
Функциональные (основные) ограничения - ограничения в виде системы a*x=(?,?,?)?, влияющие не непосредственно на решения, а на их совокупность a*x.
Косвенные (дополнительные) ограничения - ограничения вида xi ? 0, обеспечивающие неотрицательность.
Допустимые решения - варианты решений, которые удовлетворяют ограничениям.
Оптимальное решение - решение, которое по тем или иным параметрам лучше других. Оптимальное решение может быть не единственным или отсутствовать вообще. Если оптимальное решение не единственно, то значение F(x) для всех этих решений одинаково.
Эффективное решение - такое решение, что кроме него не существует другого, для которого значение F(x) были бы наилучшими.
Необходимым условием задач линейного программирования является обязательное наличие ограничений на ресурсы (сырье, материалы, финансы, спрос произведенной продукции и т.д.). Другим важным условием решения задачи является выбор критерия останова алгоритма, т.е. целевая функция должна быть оптимальна в некотором смысле. Оптимальность целевой функции должна быть выражена количественно. Если целевая функция представлена одним или двумя уравнениями, то на практике такие задачи решаются достаточно легко. Критерий останова алгоритма (или критерий оптимальности) должен удовлетворять следующим требованиям: 1) быть единственным для данной задачи;
2) измеряться в единицах количества;
3) линейно зависеть от входных параметров.
Исходя из вышесказанного, можно сформулировать задачу ЛП в общем виде: найти экстремум функции: F(x) = c1x1 c2x2 … cnxn > max (min) при ограничениях в виде равенств: a11x1 a12x2 … a1nxn = b1;
a21x1 a22x2 … a2nxn = b2;
… am1x1 am2x2 … amnxn = bm;
при ограничениях в виде неравенств: ap1x1 ap2x2 … apnxn < bp;
ar1x1 ar2x2 … arnxn < br;
… av1x1 av2x2 … avnxn < bv;
и условиях неотрицательности входных параметров: x1 ? 0; x2 ? 0; …; xn ? 0.
В краткой форме задача ЛП может быть записана так: L(x) = при условии
(или ? bi) при j =1,2,…, m, xi ? 0, i = , где x1, …, xn - входные переменные;
с1, …, cn; a11, …, anv; b1, …, bv - числа положительные, отрицательные и равные нулю.
В матричной форме эта задача может быть записана так: cx > max, при Ах ? b или Ах ? b; х ? 0 или или .
Задачи ЛП можно решить аналитически и графически.
Рассмотрим задачу и запишем ее с помощью математической модели.
Предприятие выпускает продукцию двух типов: и . Изготовляется она из четырех видов сырья: , , и . Запас сырья и расход его на единицу каждого вида продукции дан в таблице.
Вид сырья Запас сырья Расход сырья на единицу продукции вида
1923
1321
1503
1830
Прибыль производства от единицы продукции вида равна 7 денежным единицам, а от единицы продукции вида - 5 денежным единицам. Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей.
Для этой задачи целевая функция будет записана в следующем виде: F(x) = 7П1 5П2 > max, а ограничения: 2П1 3П2 ? 19;
2П1 П2 ? 13;
3П2 ? 15;
3П1 ? 18;
П1 ? 0, П2 ? 0
1.2 Основные сведения о симплекс-методе
Симплексный метод, в основу которого легла идея последовательного улучшения решения, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента: · способ определения какого-либо первоначального допустимого базисного решения задачи;
· правило перехода к лучшему (точнее, не худшему) решению;
Симплекс-метод включает два этапа: 1) определение начального решения, удовлетворяющего ограничениям;
2) последовательное улучшение начального решения и получение оптимального решения задачи.
1.3 Геометрическая интерпретация симплексного метода
Если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Путь решения задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором целевая функция принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор, в конце концов, приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано с огромными трудностями, т.к. для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е., добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущие, по значениям линейной функции (увеличение ее при отыскании максимума F>max, уменьшение - при отыскании минимума F>min).
Рис. 1. Последовательный переход к вершинам многогранника
Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере.
Пример: F = 2x1 3x2 > max при ограничениях: 2x1 3x2 ? 15, L1: 2x1 3x2 = 15;
x1 2x2 ? 8, L2: x1 2x2 = 8;
4x1 ? 16, L3: 4x1 = 16;
4x2 ? 12, L4: 4x2 = 12;
x1 ? 0, x2 ? 0. L5: x1 = 0; L6: x2 = 0.
Рис. 2. Графическое решение примера
В данном случае вместо пяти перебрали только четыре вершины, последовательно улучшая значение целевой функции.
1.4 Алгебраический смысл симплексного метода
Переход от геометрического способа решения задачи линейного программирования к симплекс-методу лежит через алгебраическое описание крайних точек пространства решений. Для реализации этого перехода сначала надо привести задачу линейного программирования к стандартной форме, преобразовав неравенства ограничений в равенства путем введения дополнительных переменных.
Стандартная форма задачи линейного программирования необходима, потому что она позволяет получить базисное решение, используя систему уравнений, порожденную ограничениями.
Стандартная форма задачи линейного программирования предполагает выполнение следующих требований.
1. Все ограничения (включая ограничения неотрицательности переменных) преобразуются в равенства с неотрицательной правой частью.
Переход к канонической форме записи производится с помощью следующих простых действий.
1. Если требуется найти минимум целевой функции f то, умножая f на (-1), переходят к задаче максимизации; т.к. min f = - max (-f).
2. Если ограничение содержит неравенство со знаком ?, то от него переходя к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную.
3. Если ограничение содержит неравенство со знаком ?, то от него переходят к равенству, вычитая из левой части дополнительную неотрицательную переменную.
4. Если в задаче какая-либо из переменных произвольна, то от нее избавляются, заменяя ее разностью двух других неотрицательных переменных.
1.5 Отыскание максимума линейной функции
Отыскание максимума линейной функции рассмотрим на примере с помощью аналитического симплекс-метода.
Прейдем к канонической форме задач ЛП, с помощью ввода дополнительных неотрицательных переменных. Все дополнительные переменные вводятся со знаком « », т.к. все неравенства имеют вид «?». Получим систему ограничений: x1 3x2 х3 = 18, 2x1 x2 x4 = 16, x2 x5 = 5, 3x1 x6 = 21.
Для нахождения первоначального базисного решения разобьем переменные на 2 группы - основные и неосновные (свободные).
В качестве основных переменных на первом шаге нужно выбрать такие переменные, каждая из которых входит в одно уравнение системы ограничений и при этом нет таких уравнений, в которые не входит ни одна из этих переменных. Количество основных переменных равно m.
Дополнительные переменные удовлетворяют этому правилу. Если выбранные по этому правилу переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях уравнений, то полученное таким образом базисное решение будет допустимым.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные переменные (по правилу): х3, x4, x5, x6, неосновные переменные: x1, x2.
Положив неосновные переменные равными нулю, т.е. x1 = 0, x2 = 0, получим первое базисное решение X1 = (0; 0; 18; 16; 5; 21), которое является допустимым (т.к. нет отрицательных чисел).
Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении: F = 2x1 3x2
F(X1) = 2 • 0 3 • 0 = 0.
Легко понять, что F можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для F с положительным коэффициентом.
Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции F.
Критерий оптимальности решения при нахождении максимума: если в выражении F отсутствуют положительные коэффициенты при неосновных переменных, то решение является оптимальным.
В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.
Шаг 4. Переход к новому решению.
1. Определить вводимую переменную.
В новый состав основных переменных вводится та из неосновных переменных, которая имеет наибольший положительный коэффициент в целевой функции. В данном случае это коэффициент при x2.
Чтобы новое опорное решение, с одной стороны, улучшая (не ухудшало) F, а с другой - было бы опорным, необходимо учитывать ограничения на рост переменной x2 (из системы ограничений). Ведь нужно сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными. Т.е. дополнительно выполняться следующие неравенства: x3 = 18 - x1 - 3x2 ? 0, x1 = 0 x3 = 18 - 3x2 ? 0, x4 = 16 - 2x1 - x2 ? 0, x4 = 16 - x2 ? 0, x5 = 5 - x2 ? 0, x5 = 5 - x2 ? 0, x6 = 21 - 3x1 ? 0, x6 = 21, x2 ? 18/3 x2 ? 16 x2 ? 5
Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной x2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при x2 при условии, что эти числа имеют разные знаки.
При оценке переменной, переводимой в основные, возможны случаи: 1) xi = , если bj и aij имеют разные знаки и bj ? 0, aij ? 0;
если bj и aij одного знака и bj ? 0, aij ? 0;
2) xi = ?, если aij = 0;
если bj = 0 и aij > 0;
3) xi = 0, если bj = 0 и aij < 0.
Так, последнее уравнение системы не ограничивает рост переменной x2, т.к. данная переменная в него не входит (или входит с нулевым коэффициентом, т.е. aij = 0).
2. Определить выводимую переменную.
Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) будет возможно, если не нарушается ни одна из полученных во всех уравнениях границ.
В данном примере наибольшее возможное значение для x2 определяется как минимум. x2 = min {18/3; 16; 5; ?} = 5.
При x2 = 5 переменная x5 - обращается в нуль и переходит в неосновные.
Уравнение, где достигается наибольшее возможное значение переменной x2, называется разрешающим.
В данном случае это третье уравнение. Выделим его рамкой.
После проделанных преобразований вновь возвращаемся к первому шагу.
Шаг 1.
1. Определим состав основных переменных: основные: x2, x3, x4, x6;
неосновные: x1, x5.
2. Выразим основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для x2): 3. x2 = 5 - x5, x2 = 5 - x5, x3 = 18 - x1 - 3 (5 - x5), x3 = 3 - x1 - 3x5, x4 = 16 - 2x1 - (5 - x5), x4 = 11 - 2x1 x5, x6 = 21 - 3x1 x6 = 21 - 3x1.
4. Получим второе базисное решение (положив неосновные переменные равными нулю): Х2 = (0; 5; 3; 11; 0; 21), которое является допустимым.
Шаг 2. Выразим F через неосновные переменные.
F = 2x1 3x2 = 2x1 3 (5 - x5) = 15 2x1 - 3x5. (2)
Определим ее значение при выбранном решении: F2 = F(X2) = 15.
Изменение значения целевой функции (т.е. ?F) можно определить как произведение наибольшего возможного значения переменной, переводимой в основные (в этом случае это х2), на ее коэффициент в выражении для F (это число 3).
В данном случае ?F1 = 5 • 3 = 15.
F2 = F1 ?F1 = 0 15 = 15.
Шаг 3. Проверка оптимальности решения.
Т.к. в выражении для F присутствуют положительные коэффициенты (в (2) перед х1), то данное решение не оптимальное, т.е. F2 не максимальное.
Шаг 4. Переход к новому решению.
1. Определим вводимую переменную.
В (2) положительный коэффициент перед х1, т.е. х1 вводим в новый состав основных переменных. Определим допустимое значение х1. x2 = 5 - x5 ? 0 т.к. х5 =0 x2 = 5 ? 0 x1 ? ? x3 = 3 - x1 3x5 ? 0 x3 = 3 - x1 ? 0 x1 ? 3 x4 = 11 - 2x1 x5 ? 0 x4 = 11 - 2x1 ? 0 x1 ? 11/2 x6 = 21 - 3x1 ? 0 x6 = 21 - 3x1 ? 0 x1 ? 7
При x5 = 1 переменная х4 обращается в 0. Третье уравнение - разрешающее. х4 - переходит в неосновные. Найдем ?F3: ?F3 = 1 • 3 = 3.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные: х1, х2, х5, х6;
неосновные: х3, х4.
2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения:
3. Получим четвертое базисное решение (положим неосновные переменные равными 0): Х4 = (6; 4; 0; 0; 1; 3), которое является допустимым.
Шаг 2. Выразим F через неосновные переменные.
F = 2x1 3x2 = 2 ( ) 3 ( ) = 24 - (5)
F4 = F(X4) = 24.
Действительно, F4 = F3 ?F3 = 21 3 = 24.
Шаг 3. Проверка решения на оптимальность.
Критерий оптимальности выполнен, т.к. коэффициенты при х3 и х4 в (5) отрицательные и удовлетворяют условию. Т.е. F3 является максимальным.
Ответ: Fmax = 24, х* =
1.5 Отыскание минимума линейной функции
При отыскании минимума линейной функции Z возможны два пути: 1) отыскать максимум функции F, полагая F = - Z и учитывая, что Zmin = - Fmax;
2) модифицировать симплексный метод: на каждом шаге уменьшать линейную функцию за счет той неосновной переменной, которая входит в выражение линейной функции с отрицательным коэффициентом.
Рассмотрим это на следующем примере.
Z = 18y1 16y2 5y3 21y4 > min при ограничениях: у1 2у2 3у4 ? 2, 3у1 у2 у3 ? 3 yi ? 0, i = 1, 2, 3, 4.
Введем дополнительные неотрицательные переменные у5 и у6 со знаком «-», т.к. неравенства имеют вид «?». Получим систему уравнений: у1 2у2 3у4 - у5 = 2, 3у1 у2 у3 - у6 = 3.
Если на первом шаге в качестве основных взять дополнительные переменные, то получим недопустимое базисное решение: (0; 0; 0; 0; -2; -3). В данном случае в качестве основных удобно взять переменные у3 и у4, коэффициенты при у3 и у4 положительны, поэтому в качестве первоначального получим допустимое базисное решение.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные: у3, у4 неосновные: у1, у2, у5, у6.
Это значение не является минимальным, т.к. значение Z можно уменьшить за счет перевода в основные любой из переменных у1 или у2, имеющих в выражении для Z отрицательные коэффициенты.
Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции Z.
Критерий оптимальности решения при нахождении минимума: если в выражении Z отсутствуют отрицательные коэффициенты при неосновных переменных, то решение является оптимальным.
В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.
Шаг 4. Переход к новому решению.
1. Определить вводимую переменную.
В новый состав основных переменных вводится та из неосновных переменных, которая имеет наибольший отрицательный коэффициент в целевой функции. В данном случае это коэффициент при у1.
Чтобы новое опорное решение, с одной стороны, улучшая (не ухудшало) Z, а с другой - было бы опорным, необходимо учитывать ограничения на рост переменной у1 (из системы ограничений). Ведь нужно сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными. Т.е. дополнительно выполняться следующие неравенства: у3 = 3 - 3у1 - у2 у6 ? 0 у2=0, у5=0, у6=0 у3 = 3 - 3у1 ? 0(1) у4 = ? 0 у4 = ? 0, у1 ? 1 у1 ? 2
Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение - границу роста переменной у1, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при у1 при условии, что эти числа имеют разные знаки.
При оценке переменной, переводимой в основные, возможны такие же случаи, как и при отыскании максимума.
2. Определить выводимую переменную.
Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) будет возможно, если не нарушается ни одна из полученных во всех уравнениях границ.
В данном примере наибольшее возможное значение для у1 определяется как минимум. у1 = min {1; 2} = 1.
При у1 = 1 переменная у3 - обращается в нуль и переходит в неосновные. Первое уравнение является разрешающим.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные: у1, у4 неосновные: у2, у3, у5, у6.
2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения: у1 = у4 =
3. Получим второе базисное решение (положив неосновные переменные равными 0): Y2 = (1; 0; 0; 1/3; 0; 0), которое является допустимым.
Шаг 2. Выразим Z через новые неосновные переменные и определим ее значение при выбранном базисном решении.
Изменение значения целевой функции (т.е. ?Z) можно определить как произведение наибольшего возможного значения переменной, переводимой в основные (в этом случае это y1), на ее коэффициент в выражении для Z (это число (- 4)).
В данном случае ?Z1 = 1 • (- 4) = - 4. Z2 = Z1 ?Z1 = 29 - 4 = 25.
Шаг 3. Проверка решения на оптимальность.
Критерий оптимальности не выполняется, т.к. коэффициент при у2 в (2) отрицателен. Т.е. Z2 не минимальное.
Шаг 4. Переход к новому решению.
1. Определим вводимую переменную.
В (2) отрицательный коэффициент перед у2, т.е. у2 вводим в новый состав основных переменных. Определим допустимое значение у2. у1 = ? 0 у3=0, у5=0, у6=0 у1 = ? 0 у4 = ? 0 у4 = ? 0, у2 ? 3 у2 ? 3/5
Положив неосновные переменные равными нулю, т.е. x1 = 0, x2 = 0, получим первое базисное решение X1 = (0; 0; 8; 1; 2), которое является допустимым (т.к. нет отрицательных чисел).
Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении: F = 3x1 3x2
F(X1) = 3 • 0 3 • 0 = 0.
Легко понять, что F можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для F с положительным коэффициентом.
Шаг 3. Проверим, доставляет ли выбранное базисное решение оптимум целевой функции F.
Критерий оптимальности решения при нахождении максимума: если в выражении F отсутствуют положительные коэффициенты при неосновных переменных, то решение является оптимальным.
В соответствии с этим критерием данное базисное решение не оптимальное. Необходимо перейти к новому базисному решению.
Шаг 4. Переход к новому решению.
1. Определить вводимую переменную.
В новый состав основных переменных вводится та из неосновных переменных, которая имеет наибольший положительный коэффициент в целевой функции. В данном случае коэффициенты при переменных равны, поэтому выбираем любой из них. Пусть это будет коэффициент при переменной x1.
Чтобы новое опорное решение, с одной стороны, улучшая (не ухудшало) F, а с другой - было бы опорным, необходимо учитывать ограничения на рост переменной x1 (из системы ограничений). Ведь нужно сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными. Т.е. дополнительно выполняться следующие неравенства: x3 = 8 - x1 - x2 ? 0, х2 =0 x3 = 8 - x1 ? 0 x1 ? 8 x4 = 1 - 2x1 x2 ? 0, x4 = 1 - 2x1 ? 0 x1 ? 1/2 x5 = 2 - x1 2x2 ? 0 x5 = 2 - x1 ? 0 x1 ? 2
При x1=1/2 переменная х4 обращается в 0. Второе уравнение - разрешающее. x4 - переходит в неосновные.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные: х1, х3, х5, неосновные: х2, х4.
2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения: x1 = , x1 = , x3 = 8 - - x2, x3 = x5 = 2 - 2x2 x5 =
Положив неосновные переменные равными нулю, получим второе базисное решение X2 = (1/2; 0; 15/2; 0; 3/2), которое является допустимым (т.к. нет отрицательных чисел).
Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении: F = 3x1 3x2 = 3 ( ) 3x2 = . (1)
F2 = F(X2) = 3/2.
Найдем ?F1 = 1/2 • 3 = 3/2.
F2 = F1 ?F1 = 0 3/2 = 3/2.
Шаг 3. Проверка оптимальности решения.
Т.к. в выражении для F присутствуют положительные коэффициенты (в (1) перед х2), то данное решение не оптимальное, т.е. F2 не максимальное.
Шаг 4. Переход к новому решению.
1. Определим вводимую переменную.
В (1) положительный коэффициент перед х2, т.е. х2 вводим в новый состав основных переменных. Определим допустимое значение х2. x1 = ? 0, х4 = 0 x1 = ? 0 х2 = ? x3 = ? 0, x3 = ? 0 х2 = 5 x5 = ? 0 x5 = ? 0 х2 = ?
При x2=5 переменная х3 обращается в 0. Второе уравнение - разрешающее. х3 - переходит в неосновные.
Шаг 1.
1. Определим состав основных и неосновных переменных: основные: х1, х2, х5, неосновные: х3, х4.
2. Выразим основные переменные через неосновные, начиная с разрешающего уравнения: 3. x1 = x2 = x5 = 9 - x3 - x4.
Положив неосновные переменные равными нулю, получим третье базисное решение X3 = (5; 3; 0; 0; 9), которое является допустимым (т.к. нет отрицательных чисел).
Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении: F = 3x1 3x2 = 3 ( ) 3 ( ) = 24 - х3. (2)
F3 = F(X3) = 24.
Найдем ?F2 = 5 • 9/2 = 45/2.
F3 = F2 ?F2 = 3/2 45/2 = 48/2 = 24.
Шаг 3. Проверка оптимальности решения.
Т.к. в выражении для F отсутствуют положительные коэффициенты при неосновных переменных, то критерий оптимальности выполнен. Х3 - оптимальное базисное решение, Fmax = F(X3) = 24.
Однако в выражении (2) для F отсутствует неосновная переменная х4 (формально она входит с нулевым коэффициентом), поэтому изменение этой переменной не повлечет за собой изменение линейной функции. Например, можно перевести в основные переменную х4; х4 = min {15; ?; 9} = 9. Переменная х5 перейдет в неосновные, однако изменения линейной функции не произойдет: ?F3 = 9 • 0 = 0. Действительно на следующем шаге получим новое базисное решение Х4 = (6; 2; 0; 9; 0), Fmax = F(X3) = 24. Учитывая, что переменная х3 = 0 (в базисном решении Х4 она осталась неосновной), а переменная х4 удовлетворяет неравенству 0 ? х4 ? 9, из системы уравнений можно получить все множество оптимальных решений задачи.
Появление вырожденного базисного решения
Рассмотрим появление вырожденного базисного решения на примере: F = 2x1 - x2 > max при ограничениях: х1 - х2 ? 2, 3х1 - 2х2 ? 6, 6х1 - 4х2 ? 14, х1 ? 0, х2 ? 0
Приведем систему неравенств к каноническому виду, путем ввода дополнительных неотрицательных переменных.
Положив неосновные переменные равными нулю, получим второе базисное решение: Х2 = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным, т.к. основная компонента x4 = 0.
Шаг 2. Выразим F через неосновные переменные и определим ее значение при выбранном базисном решении: F = 2x1 - x2 = 2 (2 x2 - x3) - x2 = 4 х2 - 2х3
F2 = F(X2) = 4.
Шаг 3. Проверка оптимальности решения.
Т.к. в выражении для F присутствуют положительные коэффициенты, то данное решение не оптимальное, т.е. F2 не максимальное.
Шаг 4. Переход к новому решению.
1. Определим вводимую переменную.
Положительный коэффициент в F перед х2, т.е. х2 вводим в новый состав основных переменных. Определим допустимое значение х2. x1 = 2 x2 - x3 ? 0, x3 = 0 x1 = 2 x2 ? 0 x2 ? ? x4 = - x2 3x3 ? 0, x4 = - x2 ? 0 x2 ? 0 x5 = 2 - 2x2 6x3 ? 0, x5 = 2 - 2x2 ? 0 x2 ? 1
Положив неосновные переменные равными нулю, получим третье базисное решение: Х3 = (2; 0; 0; 0; 2), которое является допустимым, но вырожденным.
Вывод
В данном курсовом проекте были изучены теоретические основы задач линейного программирования, история происхождения универсального метода последовательного улучшения решения, теоретические сведения о применении разновидностей симплекс-метода в жизни. Работа симплексного метода и его разновидностей была применена при решении экономической задачи нахождения оптимального плана производства.
Для упрощения нахождения оптимального плана (решения) был написан модуль, реализующий работу симплексного метода.
В результате выполнения проекта пришли к следующим выводам: 1. Роль симплексного метода достаточно велика, т.к. симплекс-метод находит применение для решения широкого круга задач линейного программирования в экономической сфере, сфере планирования и других сферах, связанных с производством, и до настоящего времени является одним из основных методов.
2. Матричный симплекс-метод более трудоемкий, чем табличный, т.к. для решения задачи матричным симплекс-методом для каждой строки составляется соответствующая формула пересчета.
3. Задачи линейного программирования могут иметь большое количество вершин (опорных решений), что вызывает вычислительные трудности. Для упрощения нахождения оптимального плана (решения) был написан модуль, реализующий работу симплексного метода. Однако несложные примеры с применением симплексного метода можно решать вручную.
4. Симплексный метод и его разновидности в настоящее время достаточно востребованы во всех сферах производства.
Список литературы
1. Введение в исследование операций. 6-е издание.: Пер. с англ. - М.: Издательский дом «Вильямс», 2001. - 912 с.: ил. - Парал. тит. англ.
2. Исследование операций в экономике: Учебное пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2001. - 407 с.
3. Линейное программирование. Ашманов С.А. - М.: Наука. Главная редакция физико-математической литературы, 1981. - 340 с.
4. Малеко Е.М. Математические методы и модели исследования операций: Учеб. пособие. - Магнитогорск: МАГУ, 2003. - 100 с.
5. Математические методы в программировании: Учебник. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 224 с.: ил. - (Профессиональное образование). - (Учимся программировать).
6. Математическое программирование: Учебное пособие. - 2-е издание, переработанное и дополненное / Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. - М.: Высшая школа, 1980. - 300 с.
7. Справочник по математике для инженеров и учащихся втузов. Бронштейн И.Н., Семендяев К.А. - М.: Наука. Главная редакция физико-математической литературы, 1981.