Контрольная работа. Контрольная работа вариант 7 задача 1
Скачать 124 Kb.
|
РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОРГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ КОНТРОЛЬНАЯ РАБОТА вариант 7 ЗАДАЧА 1. Предприятие выпускает два вида продукции А и В, для производства которых используется сырьё трех типов. На изготовление единицы изделия А требуется затратить сырья каждого типа 3, 3, 1 кг соответственно, а для единицы изделия В – 4, 1, 5 кг соответственно. Производство обеспеченно сырьем каждого типа в количестве 600, 357, 600 кг соответственно. Стоимость единицы изделия А составляет 42 руб., а единицы изделия В – 26 руб. Требуется составить план производства изделий А и В, обеспечивающий максимальную стоимость готовой продукции. Числовые данные параметров приведены в следующей таблице: а) Решить задачу симплекс-методом. б) Сформулировать двойственную задачу и привести её решение. Решение. а) Составим математическую модель задачи. Пусть х1, х2 – количество производимых изделий вида А и В соответственно. Тогда на производство будет израсходовано (3х1 + 4х2) сырья I-го типа. По условию, это количество не должно превосходить располагаемого объема этого сырья в количестве 600 единиц, т.е. 3х1 + 4х2 600. Выполняя аналогичные действия с другими типами сырья, окончательно получим систему ограничений (нетривиальные ограничения задачи): 3х1 + 4х2 600, 3х1 + х2 357, (1) х1 + 5х2 600. Количество изделий х1, х2 физически является неотрицательными (нельзя произвести отрицательное количество изделий), что дает нам тривиальные ограничения задачи: х1 0, х2 0, (2) Целевая функция представляет собой общую стоимость произведенной продукции, и эта функция в данной задаче оптимизируется на максимум: 42х1 + 26х2 max. (3) Для решения указанной задачи симплекс-методом приведем задачу (1)-(3) к каноническому виду, введя дополнительные балансовые переменные х3, х4, х5: 3 х1 + 4х2 + х3 = 600, 3х1 + х2 + х4 = 357, (4) х1 + 5х2 + х5 = 600, хi 0, , (5) 42х1 + 26х2 +0х3 + 0х4 + 0х5 max. (6) Исходный опорный план имеет вид: . Подставив компоненты в целевую функцию, получим ее значение для этого плана: Z( ) = 42х1 + 26х2 + 0х3 + 0х4 + 0х5 = 420 + 260 + 0600 + 0357 + 0600 = 0. Теперь составим первоначальную симплексную таблицу: Таблица 1.
Поскольку в индексной строке есть отрицательные числа (-42, -26), план не является оптимальным и его можно улучшить. Для изменения плана определим разрешающий столбец по максимальному модулю отрицательной оценки. Поскольку |-42| > |-26|, то переменная х1 становится базисной, а этот столбец таблицы – разрешающим столбцом. Определим разрешающую строку. Для ее определения числа в 7-ом столбце поделим на элементы разрешающего столбца. Разрешающая строка выбирается по наименьшему частному. Из последнего столбца таблицы 1 видно, что разрешающей является вторая строка с = 119. Теперь приступим к пересчету таблицы. В новой преобразованной таблице 2 (первая итерация) х4 заменяется на х1. Преобразование чисел в таблице начнем с разрешающей строки. Для этого все элементы разрешающей строки (таблица 1) делятся на разрешающий элемент «3», находящийся на пересечении разрешающей строки и разрешающего столбца. Полученные значения записываются в новую таблицу 2 в строку «х1». Все остальные клетки таблицы преобразуются по одному общему правилу: НЗ = СЗ – (АВ), где НЗ – новое значение элемента, СЗ – старое значение элемента, А – элемент на пересечении данной строки и ключевого столбца в старой таблице, В – элемент на пересечении данного столбца и ключевой строки в новой таблице. В результате получим Таблица 2. Первая итерация
Произошел переход к новым базисным переменным х1, х3, х5. При этом переменные х2, х4 являются свободными, и в опорном плане их значения равны нулю. Значения остальных получаем из нового столбца свободных членов: х1 = 119; х3 = 243; х5 = 481. Запишем опорный план в векторной форме: = (119; 0; 243; 0; 481). Этому опорному плану соответствует значение целевой функции, равное 4998. Однако в индексной строке есть еще один отрицательный элемент, поэтому полученный план не является оптимальным. Поскольку значение «-12» находится в столбце х2, поэтому х2 войдет в новый базис. Минимальное симплексное отношение (81) достигается в строке базисной переменной х3, которая выходит из базиса. Теперь пересчитаем таблицу первой итерации и получаем таблицу второй итерации. Таблица 3. Вторая итерация
Произошел переход к новому базису х1, х2, х5. При этом переменные х3, х4 являются свободными, и в опорном плане их значения равны нулю. Значения остальных получаем из нового столбца свободных членов: х1 = 92, х2 = 81, х5 = 103. Запишем опорный план в векторной форме: = (92; 81; 0; 0; 103). Этому опорному плану соответствует значение целевой функции, равное 5970. Поскольку в индексной строке больше нет отрицательных элементов, план является оптимальным: , Zmax = 5970. Итак, план выпуска, включающий 92 единицы продукции А и 81 единиц продукции В, является оптимальным. При этом будет достигнута максимальная стоимость готовой продукции. б) Двойственная задача и ее решение. Рассмотрим исходную задачу (1)-(3). Задача, двойственная задаче (1)-(3), имеет вид: F = 600y1 + 357y2 + 600y3 min (7) 3y1 + 3y2 + y3 42, (8) 4y1 + y2 + 5y3 26, yi 0, i = 1, 2, 3. (9) Оптимальное решение задачи (7)-(8) находится в индексной строке последней симплекс-таблицы и столбцах, соответствующих первоначальному базису. Отсюда находим: = (4; 10; 0). Таким образом, у1* = 4 > 0, у2* = 10 > 0, у3* = 0. Это означает, что при производстве данного вида изделий ресурсы первого и второго типов дефицитны, то есть используются полностью, а третий ресурс используется не полностью (поскольку у3* = 0). |