Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 175835
04.01.2010, 22:46
0.00 руб.
0 1 1
Образование
Здравствуйте Уважаемые эксперты! Требуется ваша помощь

Симплекс-метод.
Для производства продукции трех видов A, B и C можно использовать материал только трех сортов. При этом на изготовление единицы изделия вида A расходуется 1 кг материала первого сорта, 0 кг материала второго сорта, 6 кг материала третьего сорта. На изготовление единицы изделия вида B расходуется 0 кг материала первого сорта, 5 кг материала второго сорта, 8 кг материала третьего сорта. На изготовление единицы изделия вида C расходуется 5 кг материала первого сорта, 5 кг материала второго сорта, 0 кг материала третьего сорта. На складе фабрики имеется всего материалов первого, второго и третьего сортов в количествах соответственно 78 кг, 60 кг, 60 кг. От реализации единицы готовой продукции вида A фабрика имеет прибыль 18 рублей, вида B 17 рублей вида C 15 рублей. Составить план производства продукции, доставляющий максимальную прибыль.

Задание:
1.Составить экономическую модель задачи в табличной форме.
2.Составить математическую модель задачи. Решить задачу симплекс-методом и сделать анализ полученных результатов.

Обсуждение

давно
Асмик Гаряка
Профессор
230118
3054
10.01.2010, 03:38
общий
это ответ
Здравствуйте, kot31.

Необходимо найти (x1, x2, x3) - количество единиц изделия A, B, C соответственно.
Целевая функция 18x1+17x2+15x3[$8594$]max
Мы не можем потратить сырья больше, чем имеется на складе, поэтому ограничения имеют вид неравенств. Чтобы перейти к равенствам, добавляем избыточные переменные x4,5,6
Система ограничений Ax=b, где
Код:

   |1 0 6 1 0 0 |
A= |0 5 8 0 1 0 |
   |5 5 0 0 0 1 |

b=(78,60,60)
xi>=0
Перейдем к векторной записи задачи линейного программирования : P0=(78,60,60), P1=(1,0,5), P2=(0,5,5), P3=(6,8,0),P4=(1,0,0),P5=(0,1,0),P6=(0,0,1)
В нашем случае базис выражается легко, его составляют дополнительно введенные свободные переменные x­­4­, x­5, x­6­­.

Для получения опорного плана надо прировнять к нулю небазисные переменные, тогда получим:
x = (0; 0; 0; 0; 15; 9; 30)
Опорный план получен, и первый этап решения задачи завершен.

Для проверки на оптимальность опорного плана X1 построим первую симплекс-таблицу
Таблица 1
Код:

БП	СЧ	x1*	x2	x3	x4	x5	x6
x4	78	1 	0	5	1	0	0
x5	60	0	5	5	0	1	0
x6*	60	6	8	0	0	0	1
Y	0	-18	-17	-15	0	0	0

Алгоритм:
1) Проверяем базисные решения на оптимальность. Просматриваем знаки коэффициентов последней строки таблицы, исключая коэффициент при свободном члене. Наличие отрицательных коэффициентов в последней строке говорит о том, что решение не оптимально.
2) Выбираем из небазисных переменных ту, которая способна при введении её в базис увеличить значение целевой функции, т.е. переменную, имеющую наибольший отрицательный коэффициент в последней строке и отмечаем её звездочкой «*» - разрешающий столбец.
3) Определяем, какая из базисных переменных должна быть выведена из базиса. Для этого определяем минимальное частное от деления соответствующих свободных членов и положительных коэффициентов столбца отмеченного звездочкой. Коэффициент который находится на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом.
4) Вводимую в базис переменную выражаем через переменную, выводимую из базиса и другие небазисные переменные. Все элементы разрешающей строки делим на разрешающий элемент. Далее выражаем все остальные переменные через новую базисную. Для этого мы должны сделать равными 0 все остальные элементы разрешающего столбца таблицы 1, кроме стоящего на пересечении с разрешающей строкой. Домножаем на необходимое число разрешающую строку таблицы 1 и прибавляем к другим строкам. Получаем симплекс-таблицу 2.
Код:

БП	СЧ	x1	x2	x3*	x4	x5	x6
x4	68	0 	-4/3	5	1	0	-1/6
x5*	60	0	5	5	0	1	0
x1	10	1	4/3	0	0	0	1/6
Y	180	0	7	-15	0	0	3

Анализируем таблицу 2. В строке целевой функции есть отрицательные элементы, т.е. решение не является оптимальным, поэтому переходим к следующей симплекс-таблице. Выводим из базиса x5, вводим в базис x3.
Код:

БП	СЧ	x1	x2	x3	x4	x5	x6
x4	8	-5	-19/3	0	1	-1	-1/6
x3	12	0	1	1	0	1/5	0
x1	10	1	4/3	0	0	0	1/6
Y	360	0	22	0	0	3	3

В столбце свободных членов и в строке целевой функции нет отрицательных элементов, следовательно можно сделать вывод о том, что решение оптимально. Полученные значения удовлетворяют ограничениям задачи.
Можно выписать ответ. Значения базисных переменных и целевой функции выписываются из столбца свободных членов. Все небазисные переменные равны 0.
x1=10
x2=0
x3=12
x4=8
Предприятие будет выпускать 10 изделий 1-го вида A и 12 изделий вида C. x4=8 - это неизрасходованный остаток сырья 1-го сорта. Прибыль при этом составить 360 рублей.
5
Форма ответа