Часть полного текста документа:УНИВЕРСИТЕТ РОССИЙСКОЙ АКАДЕМИИ ОБРАЗОВАНИЯ Факультет: Бизнес, Маркетинг, Коммерция Дисциплина: Теория принятия решений Тема контрольной работы: [Задачи по четвёртому варианту] Ф.И.О. студента: Спрыжков Игорь Максимович Курс: 4. Семестр: 7. Номер зачетной книжки: 1818. Дата сдачи: _____________________ Ф.И.О. преподавателя: Асташкин С.В. Оценка: _________________________ Подпись: _________________________ Дата проверки: __________________ ЗАДАЧА 1 УСЛОВИЕ Решить симплекс-методом задачу, предварительно приведя её к каноническому виду: x1 - x2 - x3 + 7x4 > max -x1 + 2x2 - x3 + x4 ? 2 2x1 + x2 + x3 - 2x4 ? 12 2x1 + 3x2 + 4x3 + 2x4 ? 6 xj ? 0, j = 1, 2, 3, 4 РЕШЕНИЕ Общий вид задачи линейного программирования в канонической форме: ?aij = bi, i = 1, 2, ..., n xj ? 0, j = 1, 2, ..., n, n+1, n + m ?pjxj > max Экономико-математическая модель рассматриваемой задачи в канонической форме будет иметь вид: -1x1 + 2x2 - 1x3 + 1x4 + 1x5 + 0x6 + 0x7 = 2 2x1 + 1x2 + 1x3 - 2x4 + 0x5 + 1x6 + 0x7 = 12 2x1 + 3x2 + 4x3 + 2x4 + 0x5 + 0x6 + 1x7 = 6 xj ? 0, j = 1, 2, ..., 7 x1 - x2 - x3 + 7x4 + 0x5 + 0x6 + 0x7 > max Т.е. в ней линейная форма максимизируется, все ограничения являются равенствами, все переменные удовлетворяют условию неотрицательности. Система уравнений имеет предпочитаемый вид: базисными переменными являются переменные Х5, Х6, Х7, правые части неотрицательны. Исходное опорное решение, дающее координаты исходной угловой точки, имеет вид Х = (0, 0, 0, 0, 2, 12, 6)т. Все остальные вычисления и действия удобно производит в табличной форме (табл. 1 - 3). Решение задачи потребовало три итерации, каждой из которых соответствует симплекс-таблица. В первую строку первой симплекс-таблицы занесены все данные первого уравнения, во вторую - второго и т.д. В каждой из таблиц во втором столбце (Бx) указаны базисные неизвестные. Неизвестные, не входящие в базис, равны нулю. Значения базисных неизвестных записаны в третьем столбце (X0). Нижний элемент этого столбца является значением критерия оптимальности на данном шаге. В первом столбце (Pj) представлены коэффициенты при базисных неизвестных, взятые из критерия оптимальности. Каждый из столбцов X1 - X4 соответствует основным переменным задачи, а столбцов X5 - X7 - дополнительным переменным задачи. Последние элементы этих столбцов образуют нижнюю строку, содержащую элементы ?J. С их помощью определяется, достигнут ли оптимум, а если не достигнут, то какое небазисное неизвестное следует ввести в базис, чтобы улучшить план. Элементы последнего столбца (?) позволяют найти то из прежних базисных неизвестных, которое следует вывести из базиса, чтобы улучшить план. Разрешающий элемент, расположенный на пересечении столбца, вводимого в базис неизвестного, и строки неизвестного, выводимого из базиса, выделен в каждой таблице. Рассмотрим первую симплексную таблицу решения задачи. План задачи находится в столбцах Бх и Х0. Элементы столбцов Х1 - Х7 являются коэффициентами замещения неизвестных. Они показывают, в каком соотношении любые из неизвестных могут заменить базисные переменные в плане данного шага. Элементы нижней строки столбцов Х1 - Х7 показывают размер уменьшения значения критерия оптимальности от замены базисных неизвестных Хj. Показатель ?j рассчитывается перемножением элемента первого столбца таблицы (Pj) на элемент столбца Хj с последующим вычитанием соответствующего элемента Pj. После нахождения L0 и ?j, проверяется условий оптимальности (все ?j > 0) и неразрешимости (если найдется хотя бы один ?j < 0 такой, что все элементы соответствующего столбца отрицательны). Наличие отрицательных ?j свидетельствует о том, что найденный план производства не является оптимальным, так как имеются возможности увеличения прибыли. ............ |