Задачи з теорії прийняття решений

УНІВЕРСИТЕТ РОСІЙСЬКОЇ АКАДЕМІЇ ОБРАЗОВАНИЯ.

Факультет: Бізнес, Маркетинг, Комерція Дисципліна: Теорія прийняття рішень Тема контрольної роботи: [Завдання по четвертому варианту].

Ф.И.О. студента: Спрыжков Ігор Максимович Курс: 4. Семестр: 7. Номер залікової книжки: 1818.

Дата здачі: _____________________ Ф.И.О. викладача: Асташкин С. В. Оцінка: _________________________ Підпис: _________________________ Дата перевірки: __________________.

Завдання 1.

Условие.

Вирішити симплекс-методом завдання, попередньо привівши її до канонічному виду: x1 — x2 — x3 + 7×4 > max.

— x1 + 2×2 — x3 + x4? 2.

2x1 + x2 + x3 — 2×4? 12.

2x1 + 3×2 + 4×3 + 2×4? 6 xj? 0, j = 1, 2, 3, 4.

Решение.

Загальний вид завдання лінійного програмування в канонічної форме:

Saij = bi, і = 1, 2, …, n xj? 0, j = 1, 2, …, n, n+1, n + m.

Spjxj > max.

Экономико-математическая модель аналізованої завдання у канонічної формі матиме вид:

— 1×1 + 2×2 — 1×3 + 1×4 + 1×5 + 0×6 + 0×7 = 2.

2x1 + 1×2 + 1×3 — 2×4 + 0×5 + 1×6 + 0×7 = 12.

2x1 + 3×2 + 4×3 + 2×4 + 0×5 + 0×6 + 1×7 = 6 xj? 0, j = 1, 2, …, 7×1 — x2 — x3 + 7×4 + 0×5 + 0×6 + 0×7 > 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 свідчить у тому, що знайдений план виробництва перестав бути оптимальним, оскільки є можливості збільшення прибыли.

Як який дозволить шпальти (невідомої) то, можливо взятий будь-який стовпець, котрій оціночний коефіцієнт негативний. Однак за тих що дозволяє стовпець зазвичай приймають стовпець, котрій негативний оціночний коефіцієнт приймає найменше значение.

Для визначення невідомого, що слід вивести ринок із базису, використовують показники останнього шпальти ?. Він отримано шляхом розподілу елемента третього шпальти Х0 на елемент шпальти невідомого, який вводимо в базис такого кроку. Параметр? показує, який ресурс нас лімітує, тому з базису виводиться змінна, відповідна найменшій позитивному значенням ?.

Рядок у новій таблиці, відповідна роздільною, виходить з роздільною рядки розподілом всіх елементів на що дозволяє элемент.

Стовпчики, відповідні базисним невідомим, є поодинокими, причому одиниця слід за перетині рядки — і шпальти з переменными.

Після заповнення нової таблиці (всяка нова таблиця є новою по відношення до аналізованої) знову перевіряється виконання умов оптимальності і разрешимости задачи.

У третій симплекс-таблице виконується умова оптимальності. Рішення завдання припиняється. Максимальне значення лінійної форми: LОПТ = 18.

Відповідь: оптимальне рішення x* = (0.5; 0; 0; 2.5), тобто. х1* = 0.5, х2* = 0, х3* = 0, х4* = 2.5.

Таблиця 1.

Симплексная таблиця першого плану завдання | |1 |2 |3 |4 | |борошно 1 сорта,|0.5 |0.5 |0 |0 | |кг | | | | | |борошно 2 сорта,|0 |0 |0.5 |0.5 | |кг | | | | | |маргарин, кг |0.125 |0 |0 |0.125 | |яйце, прим. |2 |1 |1 |1 | |прибуток, за 1|14 |12 |5 |6 | |кг | | | | |.

Потрібна визначити добовий план випікання хліба, максимізує прибыль.

Решение.

0.5×1 + 0.5×2 + 0· x3 + 0· x4? 290.

0· x1 + 0· x2 + 0.5×3 + 0.5×4? 150.

0.125×1 + 0· x2 + 0· x3 + 0.125×4? 50.

2x1 + 1×1 + 1×3 + 1×4? 1280.

14×1 + 12×2 + 5×3 + 6×4 > max.

Решта обчислення і дії зручно виробляє в табличній формі (табл. 8 — 11).

Таблиця 8.

Симплексная таблиця першого плану завдання Pi |Бx |X0 |14 |12 |5 |6 |0 |0 |0 |0 |? | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 | | |0 |x5 |290 |0.5 |0.5 |0 |0 |1 |0 |0 |0 |580 | |0 |x6 |150 |0 |0 |0.5 |0.5 |0 |1 |0 |0 |? | |0 |x7 |50 |0.125 |0 |0 |0.125 |0 |0 |1 |0 |400 | |0 |x8 |1280 |2 |1 |1 |1 |0 |0 |0 |1 |640 | | |?j |0 |-14 |-12 |-5 |-6 |0.

|0 |0 |0 | | |Таблиця 9.

Симплексная таблиця другого плану завдання Pi |Бx |X0 |14 |12 |5 |6 |0 |0 |0 |0 |? | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 | | |0 |x5 |90 |0 |0.5 |0 |-0.5 |1 |0 |-4 |0 |180 | |0 |x6 |150 |0 |0 |0.5 |0.5 |0 |1 |0 |0 |? | |14 |x1 |400 |1 |0 |0 |1 |0 |0 |8 |0 |? | |0 |x8 |120 |0 |-1 |1 |1 |-4 |0 |0 |1 |- | | |?j |5600 |0 |-12 |-5 |-8 |0 |0 |112.

|0 | | |Таблиця 10.

Симплексная таблиця третього плану завдання Pi |Бx |X0 |14 |12 |5 |6 |0 |0 |0 |0 |? | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 | | |12 |x2 |180 |0 |1 |0 |-1 |2 |0 |-8 |0 |? | |0 |x6 |150 |0 |0 |0.5 |0.5 |0 |1 |0 |0 |300 | |14 |x1 |400 |1 |0 |0 |1 |0 |0 |8 |0 |? | |0 |x8 |300 |0 |0 |1 |0 |-2 |0 |-8 |1 |300 | | |?j |7760 |0 |0 |-5 |-4 |24 |0 |16 |0 | | |.

Таблиця 11.

Симплексная таблиця четвертого плану завдання Pi |Бx |X0 |14 |12 |5 |6 |0 |0 |0 |0 | | | | | |x1 |x2 |x3 |x4 |x5 |x6 |x7 |x8 | | |12 |x2 |180 |0 |1 |0 |-1 |2 |0 |-8 |0 | | |5 |x3 |300 |0 |0 |1 |1 |0 |2 |0 |0 | | |14 |x1 |400 |1 |0 |0 |1 |0 |0 |8 |0 | | |0 |x8 |300 |0 |0 |0 |-1 |-2 |-2 |-8 |1 | | | |?j |9260 |0 |0 |0 |1 |12 |10 |16 |0 | | |.

Відповідь: добовий план випуску продукції: хліб 1-го виду — 400 кг, 2-го виду — 180 кг 3-го виду — 300 кг, 4-го виду — 0 кг.

Список використаних источников.

. Зубков М. Я. Математичні структури та математичне моделювання економіки: Навчальний посібник. Вип. 3 В. Математичне програмування. -.

М.: Вид-во УРАО, 1996. — 68 з.. Альошина І.Ф. Аналіз і - оцінка господарських рішень: Методичні вказівки до вивчення курсу. — М.: Вид-во РОУ, 1996. — 28 с.