Методическое пособие для выполнения контрольной работы по дисциплине
жүктеу/скачать 0.49 Mb.
|
Алгоритм симплекс-методаНаходят опорный план Составляют симплекс-таблицу Выясняют разрешимость ЗЛП Если существуют , тогда определяют номер разрешающего столбца по максимуму | | Для данного к определяют номер разрешающей строки по минимуму. для всех положительных элементов разрешающего столбца симплекс-матрицы. По формулам определяют , и . Составляют новую симплекс-таблицу. См. пункт 3. Задача. Определить план изготовления изделий А, В и С, обеспечивающий максимальный их выпуск в стоимостном выражении с учётом ограничений на возможное использование сырья трёх видов.
Составим математическую модель данного производства. Введем следующие обозначения: x1 – выпуск изделий А; x2 – выпуск изделий В; х3 – выпуск изделий С. Запишем выражение для целевой функции (общая стоимость проданных изделий, которая должна быть максимальной): Q=9x1+10x2+16x3→max. Исходя из запасов сырья и неотрицательности количества выпускаемых изделий, составляем условия ограничения: Для решения задачи симплекс-методом переведем ЗЛП в основную форму, превратив неравенства в равенства, для чего введем новые неотрицательные переменные х4, х5, х6: 18х1 + 15х2 +12х3 + х4 = 360 6х1 + 4х2 + 8х3 +х5 = 192 5х1 + 3х2 +3х3 + х6 = 180 Введенные новые переменные имеют следующий экономический смысл: х 4 – неизрасходованное количество сырья А; х5 - неизрасходованное количество сырья В; х6 - неизрасходованное количество сырья С. Векторы для новых переменных Р4 = , Р5 = , Р6 = являются единичными, т.е. введенные переменные {х4, х5, х6} представляют базис, а остальные переменные {х1,х2, х3} являются свободными, следовательно, опорный план имеет вид: Х=( ). Значение целевой функции равно Qo=9·0+10·0+16·0=0 (усл. ед.): ничего не произвели – ничего не получили. Таблица. Исходная симплекс-таблица данной задачи
Рассчитаем исходные значения целевой функции Qo=СбВ=360·0+192·0 + 180·0=0 и вспомогательных величин Δj=CбPj–Cj: Δ1 = P1Cб–C1=18·0+6·0+5·0–9=-9, Δ2 = P2Cб–C2=15·0+4·0+3·0–10=-10 Δ3 = P3Cб–C3=12·0+8·0+3·0–16=-16 Отрицательные числа Δj свидетельствуют о возможности увеличения общей стоимости продукции и показывают насколько увеличится сумма при введении в план единицы продукции. Максимальное значение модуля вспомогательной величины Δj равно 16, следовательно, номер разрешающего столбца к=3. Для данного столбца все > 0. Находим минимальное значение : min = min{30, 24, 60} = 24. Следовательно, номер разрешающей строки r = 2. Таким образом, разрешающий элемент = 8. Вводим в базис вектор Р3, выводим из базиса вектор Р5. Все элементы данной новой строки вычисляются делением на разрешающий элемент Остальные элементы вычисляются по правилу треугольника, согласно которому находятся три числа: число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы (число А); число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы и столбца, соответствующего вектору, вводимому в базис (число С); число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора (число В). Искомый элемент новой симплекс-таблицы вычисляется по формулам Жордана-Гаусса: А-В∙С. Таким образом, новая симплекс-таблица представлена в следующей таблице.
Так как среди чисел существует отрицательное значение то, следовательно, план не является оптимальным. Разрешимость задачи остается в силе, так как все коэффициенты столбца Р2 положительны. Разрешающий столбец , т.к. . Этот столбец нужно ввести в базис. Для определения разрешающей строки найдём минимум min =min =min =8. Следовательно, разрешающая строка и разрешающий элемент равен . Первая строка новой симплекс таблицы получается путём деления исходной строки на 9.
Векторы Р2, Р3 и Р6 образуют базис, соответствующие числа равны нулю. Остальные элементы симплекс-таблицы пересчитываются по правилу треугольника: =A-BC=24-8*1/2=20 =108-8*3/2=96 = - * =384-8(-2)=400 =3/4-1/2*1=1/4 =11/4-3/2*1=5/4 =0-1/2*1/9=-1/18 =1/8-1/2*(1/6)=1/8+1/12=5/24 =3-1(-2)=5 =0-1/9(-2)=2/9 =2-(-1/6)(-2)=2-1/3=5/3 Так как все , то полученный план является оптимальным: . Экономическая интерпретация полученного решения: для получения максимальной стоимости нужно произвести 8 изделийВ; 20 изделий С; при этом сырьё I и IIбудет израсходовано полностью, останется 96 кг сырья III. Выпуск продукции в денежном выражении составляет 400 усл. ед. Задание 2. Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определённое время обработки на всех четырёх устройствах I, II, III, IV.
Пусть время работы на устройствах, соответственно, 84-2m, 42-n, 21+k и 42 часа. В соответствии со своими индивидуальными данными (m – число гласных букв в фамилии студента, n – число гласных букв в полном имени студента, k – число гласных букв в отчестве студента) определите, какую продукцию и в каких количествах следует производить. Рынок сбыта для каждого продукта неограничен. Временем, требуемым для переключения устройства в зависимости от вида продукции, можно пренебречь. Рассмотреть задачу максимизации прибыли. жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||