- •Принятие управленческих решений с использованием задачи линейного программирования
- •Графический метод решения задачи линейного программирования
- •Решение
- •Задачи линейного программирования, не требующие для решения специальных методов
- •Решение
- •Симплекс-метод. Определение оптимальной производственной программы предприятия
- •Решение
Решение
Пусть − количество выпускаемой продукцииi-гo вида, тогда система неравенства, отражающих ограничения на имеющийся объем ресурсов по каждому виду, будет следующей
Общая прибыль составит
.
Переменные не могут быть меньше нуля, так как выпуск продукции не может быть отрицательным
.
Прежде чем решить задачу симплекс-методом, необходимо математическую постановку данной задачи привести к общей постановке задачи линейного программирования (канонической форме), т.е. от ограничений-неравенств перейти к ограничениям-равенствам. Для этого в каждое из неравенств вводится по одной дополнительной переменной: В результате получаем
С экономической точки зрения дополнительные переменные характеризуют объем неиспользуемого в плане ресурса i-го вида.
Для построения первой симплекс-таблицы необходимо определить начальное допустимое базисное решение. Данная задача относятся к задачам линейного программирования с явно выраженным начальным опорным планом. В качестве начальной выбирается ситуацию, когда предприятие ничего не выпускает, т.е. . Эти значения переменных можно принять за начальное допустимое базисное решение. При этом все имеющиеся ресурсы не расходуются, т.e. . Переменные называются свободными, a − базисными. При решении задачи линейного программирования симплекс-методом свободные переменные всегда равны нули, а базисные переменные − больше нуля (в некоторых случаях базисная переменная может принимать нулевое значение, тогда такой базис называется вырожденным).
Для заполнения первой симплекс-таблицы необходимо представить математическую постановку задачи линейного программирования (ограничения-равенства и целевую функцию ) в удобном для этого виде
.
Первая симплекс-таблица имеет вид, представленный в табл. 1.7.
Таблица 1.7
Базисная переменная |
Свободный член |
Коэффициент при свободной переменной | ||
↑ |
|
| ||
|
24 |
-5 |
7 |
4 |
|
80 |
10 |
5 |
20 |
|
10 |
5 |
2 |
1 |
|
6 |
2 |
1 |
1 |
F |
0 |
-18 |
-12 |
-8 |
Процесс отыскания оптимального решения заключается в переходе от одной симплекс-таблицы к другой, пока не будет достигнуто оптимальное решение (план) задачи.
Для получения новой симплекс-таблицы необходимо воспользоваться следующим алгоритмом:
Выбирается генеральный столбец, т.е. столбец с наибольшим по модулю отрицательным коэффициентом в строке .
В генеральном столбце определяется генеральный коэффициент по минимуму отношения
,
где - i-й коэффициент в столбце "Свободный член";
- i-й коэффициент в генеральном столбце.
На место генерального коэффициента записывается величина, обратная генеральному коэффициенту
.
Все значения коэффициентов генеральной строки, т.е. строки, где находится генеральный коэффициент, делятся на значение генерального коэффициента и записываются в эту же строку.
Все значения коэффициентов генерального столбца делятся на значение генерального коэффициента и записываются в тот же столбец с противоположным знаком.
Все остальные коэффициенты находятся по правилу прямоугольника
Используя вышеприведенный алгоритм, устанавливается, что генеральным будет столбец, соответствующий свободной переменной , а генеральный коэффициент находится в строке, соответствующей базисной переменной, т.е.. Поменяв местами переменныеи(базисная переменнаястановится свободной, а свободная переменная− базисной) по рассмотренному выше алгоритму, выстраивается вторая симплекс-таблица (табл. 1.8).
Таблица 1.8
Базисная переменная |
Свободный член |
Коэффициент при свободной переменной | ||
|
↑ |
| ||
|
14 |
-1 |
5 |
3 |
|
60 |
-2 |
1 |
18 |
|
2 |
|
|
|
|
2 |
|
|
|
F |
36 |
|
|
|
Анализируя полученные значения коэффициентов при свободных переменных в строке целевой функции F, устанавливаем, что данное решение еще не является оптимальным, так как есть отрицательные значения коэффициентов , следовательно, необходимо продолжить решение задачи. Повторив указанные выше действия, выстраивается третья симплекс-таблица (табл. 1.9)
Таблица 1.9
Базисная переменная |
Свободный член |
Коэффициент при свободной переменной | ||
|
|
↑ | ||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
|
|
|
|
Далее строится четвертая симплекс-таблица (табл. 1.10).
Таблица 1.10
Базисная переменная |
Свободный член |
Коэффициент при свободной переменной | ||
|
|
| ||
|
1 |
|
|
|
|
5 |
|
|
|
|
1 |
|
|
|
|
3 |
|
|
|
F |
54 |
|
|
|
Все значения коэффициентов при свободных переменных в строке целевой функции неотрицательны, следовательно, получено оптимальное базисное решение (план)
.
Таким образом, при выпуске предприятием продукции вида А в объеме 1 ед., вида В − 1 ед., вида С − 3 ед. максимальная прибыль составит 54 тыс.руб. При этом материалы, оборудование I и II групп используется полностью, а рабочая сила на 5 человек недоиспользуется.