Лабораторная - Разработка производственных и управленческих решений
Лабораторная - Разработка производственных и управленческих решений
КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
им. А.Н. Туполева
ФИЛИАЛ «ВОСТОК»
Расчетно-графическая работа
по дисциплине
«Разработка производственных и управленческих решений»
Вариант 17
Выполнил: ст. гр. 21404
Овчинникова О.В.
Проверил: Гашева М.В.
Чистополь 2009
Решение задачи симплексным методом
Симплекс метод- это метод упорядочивания перебора опорных планов, упорядочивание в данном случае обеспечение последовательным перебором опорных планов с монотонным изменением значения целевой функции в сторону возрастания(убывания).
Исходные данные:
Предприятие занимается производством 2 видов продукции 1 и 2, для их производства требуется 3 вида сырья. На изготовление единицы изделия 1 требуется сырья каждого вида
кг, а для изделия 2-
кг. Стоимость единицы изделия 1 -
, а для 2-
т.р. Необходимо составить такой план производства изделий, при котором прибыль от производства и реализации данной продукции будет максимальной. На предприятии имеется сырья в количестве .
606
802
840
9
15
15
27
15
3
5
6
Решение:
Составим экономико-математическую модель задачи. Для этого обозначим
- количество изделий А.
- количество изделий В. Эта задача является задачей оптимального использования сырья, поэтому система организации имеет вид:
+
≤606
9
+27
≤606
15
+15
≤802 (1)
15
+3
≤840
Где справа стоит количество каждого вида сырья, которые не может быть превышено в процессе производства изделий.
≥0,
≥0 (2)
Целевая функция представляет собой общую стоимость произведенной продукции.
С=5
+6х2
=> макс. (3)
Для решения задач симплекс методом приводят ее к каноническому виду, введя дополнительные балансовые переменные х3
,х4
,х5
, которые означают остатки сырья соответственно 1,2, 3 типов, при этом неравенство преобразуется в уравнение, т.е. левая часть сбалансирована с правой.
9
+27
+ х3
≤606
15
+15
+ х4
≤802 (4)
15
+3
+х5
≤840
х3
, х4
, х5
- остатки 1,2,3 вида сырья.
х1
,х2,
х3
,х4,
х5
≥ 0 (5)
С=5
+6х2
+0х3
+0х4
+0х5
=> макс. (6)
Систему (4) можно записать в другом виде:
р1
х1
+р2
х2
+р3
х3
+р4
х4
+р5
х5
=р0
р1
р2
р3
р4
р5
р0
Здесь векторы р3
р4
р5
имеют предпочтительный вид, т.е являются единичными в одном из компонентов и нулевыми во всех остальных компонентах. Р0
- называется столбцом свободных членов системы ограничений, для решения системы (4)-(6) симплекс методом необходимо иметь опорный план, т.е. допускаются решения системы (4), для этого надо разделить на 2 группы- базисные и свободные. Сначала выбираем базисные, в качестве их выбирают векторы, имеющие предпочтительный вид, т.е в данном случае р3
р4
р5.
им соответствуют базисные переменные х3
, х4
, х5
системы (4). Остальные переменные х1
,х2
- будут свободными, при получении базисного решения все свободные переменные =0. Подставив в (4) х1
=х2
=0, получаем остальные компоненты опорного плана х3
=606, х4
=802,х5
=840. В векторном виде этот опорный план выглядит так: х0
=(0,0,606,802,840). Подставив компоненты х0
в целевую функцию (6) получаем значение целевой функции=0. С (х0
)=0.
1 симплексная таблица( опорный план в виде симплекс таблицы)
Оценка базисных переменных
Базисные переменные
Свободные члены
5
6
0
0
0
С
Х
Р0
Р1
Р2
Р3
Р4
Р5
0
Х3
606
9
27
1
0
0
0
Х4
802
15
15
0
1
0
0
Х5
840
15
3
0
0
1
С
0
-5
-6
0
0
0
Переход к новому опорному плану, выбор разрешающего столбца: