Реферат Курсовая Конспект
Методика отыскания оптимального решения - раздел Экономика, УЧЕБНО-МЕТОДИЧЕСКИЙ КОмПЛЕКС дисциплины Методы отыскания оптимальных экономических решений и специальностей Рассмотрим Задачу Оптимизации Плана Производства (Задача 1 Тема 2): ...
|
Рассмотрим задачу оптимизации плана производства (задача 1 тема 2):
При x1 ≥0 и x2≥0
Суммарная прибыль
F =2x1+3x2 → max
С помощью дополнительных переменных перейдем от стандартного вида к каноническому:
Для нахождения базисного решения необходимо выделить 2 группы переменных:
- основные, т.е. такие m-переменных, каждая из которых входит только в одно из m-уравнений системы ограничений, при этом нет таких уравнений, в которые бы не входила ни одна из этих переменных. Коэффициенты основных переменных должны быть равны +1;
- не основные – все остальные переменные. Для реализации задачи симплекс-методом используют следующий алгоритм:
Первый шаг:
Основные переменные:х3, х4, х5, х6.
Неосновные переменные: х1, х2.
Bыразим основные переменные через неосновные:
Подчеркнутое уравнение является разрешающим уравнением для второго шага.
Неосновные элементы считаем равными 0: х1=0, х2=0, тогда базисное решение A1(0;0;18;16;5;21). Это одно из возможных решений, но нельзя считать, что оно является оптимальным. Оно соответствует началу координат графика О (0;0)
Далее выражают функцию оптимизации через неосновные переменные:
F =2x1+3x2 → max
Для принятия решения важно проанализировать функцию F. Если есть хотя бы при одной переменной коэффициент К>0 в задаче на max, то рассматривают поведение функции F при увеличении значения соответствующей переменной.
Рассмотрим переменную х2, , т.к. К=3>0, то при увеличении значения х2 значение функции F возрастает, значит, решение А1 не является оптимальным.
Можно рассматривать и переменную х1, т.к. коэффициент при x1 =2>0. Однако, при выборе анализируемой переменной оценивают коэффициент при ней. Как правило, чем выше коэффициент, тем менее трудоемкой является задача в своем решении.
Следовательно, рассматриваем переменную х2, и она переходит из неосновных в основные. Геометрический смысл преобразований сводится к переходу к следующей вершине многогранника возможный решений, где значение функции становится лучшее.
Основная переменная должна иметь коэффициент К=1.
Для приведения системы ограничений в решаемый вид на следующем этапе для новой основной переменной, выражая ее из всех уравнений системы ограничений при условии, что все остальные переменные = 0.
Выбирают самый минимальный разрешающий коэффициент (х2 = 5), который в нашем примере соответствует 3-ему уравнению. Тогда х5 переходит в неосновные переменные. Уравнение, из которого была выражена переменная, называется разрешающим (х5 = 5 - х2).
Второй шаг:
Основные переменные:х2, х3, х4, х6.
Неосновные переменные: х1, х5.
Выразим новые основные переменные через неосновные, начиная с разрешающего уравнения:
Подставим вместо х2 его выражение:
|
Неосновные переменные приравниваются к 0: х1 = 0 и х5 = 0, тогда второе базисное решение А2(0;5;3;11;0;21). Геометрически мы перешли к вершине А (0;5) в многоугольнике решений (Тема 2, раздел 2). Выразим функцию F через неосновные переменные:
F2=2x1+3x2=2x1+3(5-x5)=2x1+15-3x5
При увеличении значения переменной х1 значение функции F2 будет увеличиваться, значит, решение А2 не является оптимальным.
Найдем разрешающие коэффициенты для переменной х1:
Выбираем самый минимальный разрешающий коэффициент x1=3. Уравнение, из которого была выражена переменная (x3 = 3 - x1+ 3x5) является разрешающим. Переменная x3 переходит в неосновные переменные, а х1 - в основные.
Третий шаг
Основные переменные: х1, х2, х4, х6.
Неосновные переменные:х3, х5.
|
Базисное решение А3 (3;5;0;5;0;12) соответствует вершина Е(3;5)
F3=2x1+3x2=2(3-x3+3x5)+3(5-x5)=21-2x3+3x5
При х3 =0, х5 = 0 значение F3 = 21, что больше F2 = 15 на 6.
Увеличивая значение х5 значение функции будет также увеличиваться. Переведем х5 в основные переменные.
Найдем разрешающие коэффициенты х5:
|
Разрешающим уравнением является х4 = 5 + 2х3 - 5х5, из которого .
Переменная х4 переходит в неосновные.
Четвертый шаг
Основные переменные:х1, х2, х5, х6.
Неосновные переменные:х3, х4.
Базисное решение А4 (6;4;0;0;1;3) соответствует вершине В (6;4)
Это выражение функции не содержит переменных с положительными коэффициентами. При х3=0, х4=0 значение F4 является максимальным. Зная экономический смысл переменных, получаем, что максимальное значение прибыли – 24 руб. при реализации продукции А – 6 ед., продукции В – 4 ед. Дополнительные переменные х3, х4, х5, х6 показывают разницу между запасами ресурсов каждого вида и их потреблением на производство продукции А и В, т.е. остатки ресурса S1=0, S2=0, S3=1, S4=3 ед.
Таким образом, задачу на максимум решают до тех пор, пока в выражении линейной функции через неосновные переменные останутся отрицательные коэффициенты при неосновных переменных.
При отыскании минимума функции возможны 2 варианта:
1. отыскивать максимум функции, учитывая, что Zmin= - Fmax;
2. на каждом шаге рассматривать неосновные переменные, при которых стоят отрицательные коэффициенты, т.к. увеличивая значения этих переменных, значение функции будет уменьшаться, т.е. постепенно стремиться к min.
Критерием оптимальности при отыскании min функции является следующее правило:
Если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение является оптимальным. |
При решении задачи симплекс-методом не всегда возможно сразу выделить допустимое базисное решение.
Например:
F=x1+2x2 → max
x1 ≥ 0 и x2 ≥ 0.
Решение:
1. Вводим дополнительные переменные:
2. Выделим основные переменные х3, х4, х5 неосновные переменныех1, х2
3. Выразим основные переменные через неосновные:
Базисное решение А1 (0;0;-1;3;3) является недопустимым, т.к. х3< 0.
В таком случае в системе уравнений выбирают то уравнение, которое содержит отрицательный свободный член (х3= -1 - х1 + х2).
Необходимо увеличить значение х3. Это возможно за счет увеличения переменных, входящих в уравнение с положительным коэффициентом (+х2).
При х2 =1 и х3 =0. Тогда х3 станет неосновной, х2 - основной переменными.
Найдем разрешающий коэффициент для переменной х2
x2=min{1;3}=1
Тогда уравнение x3= -1 + x2 – x1 является разрешающим
На втором шаге основными переменными станут х2, х4, х5, а неосновными х1, х3.
Базисное решение А1(0; 1; 0; 2; 3) является допустимым
F=x1+2x2=x1+2(1+x1+x3)=2+3x1+2x3, и т.д.
Бывают задачи, когда допустимое базисное решение возникает со 2, 3 и т.д. шагов.
Если базисное решение является недопустимым и для его улучшения есть возможность выбора переменной, то рекомендуют выбрать такую неосновную переменную, которая определит в качестве разрешающего то уравнение системы, где содержится отрицательный свободный член, и перевести в основные ту неосновную переменную, которая в это уравнение входит с положительным коэффициентом.
Если базисное решение недопустимое, а в уравнении, содержащем отрицательный свободный член, отсутствует неосновная переменная с положительным коэффициентом, то допустимое базисное решение получить невозможно, т.к. условия задачи являются противоречивыми.
При решении экономических задач симплекс-методом могут возникнуть ситуации, когда оптимальное решение будет неединственным (альтернативным), или конечный оптимум может отсутствовать. В первом случае, выбор оптимального варианта зависит от эксперта, принимающего решения, во - втором случае необходимо задать дополнительные условия – ограничений для принятия решения.
– Конец работы –
Эта тема принадлежит разделу:
федеральное государственное бюджетное образовательное учреждение... высшего профессионального образования... ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СЕРВИСА...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Методика отыскания оптимального решения
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов