Лінійне програмування
Варіант № 6
Завдання № 1. Рішення симплексним методом:
(1.1)
(1.2)
(1.3)
Задача (1.1) - (1.3) є спільним завданням лінійного програмування (ЛП), оскільки система (1.1) складається з нерівностей, вводячи додаткові невідомі х3 > 0, х4 > ; 0 і додаючи їх до лівих частинах першого і другого нерівності і відбираючи невідому х5 > 0 від лівої частини третьої нерівності, домножимо третій нерівність на -1, отримаємо основну задачу ЛП види:
(1.4)
(1.5)
(1.6)
Чи не виконуючи додаткових перетворень, визначаємо, що основна форма (1.4) - (1.6) одночасно є і канонічної формою задачі ЛП.
Задача (1.4) - (1.6) канонічна, застосуємо для їх вирішення стандартний симплекс метод. Запишемо систему обмежень і початкове значення цільової функції у вихідну симплекс таблицю. br/>
Таблиця № 1
Базісиx0x1 x2 x3x4x5Ключевое отношеніех345 -2 100-2х4 4-120102 х5-4-1 -1 0014f0-1 -2 000
Так як завдання максимізації, то в індексному рядку відшукаємо найменший елемент - це -2, цей елемент лежить в основі ключового стовпця, який вказує на елемент, що вводиться в базис. Підрахувавши ключові відносини, знаходимо найменші, яке вказує на невідоме, що вводиться в базис, але позитивне - це 2. Отже, будуємо нову таблицю і вписуємо нові базисні невідомі, замість x 4 увійде x 2 .
Таблиця № 2
Базісиx0x1x2x3x4x5Ключевое отношеніех38401102х22-1/2101/204х5-2-1 1/2001/211 1/3f4-20010
У новій таблиці (Таблиця № 2) розраховуємо і записуємо ключову рядок, вона виходить розподілом всіх елементів відповідного рядка вихідної таблиці на ключовий елемент, тобто на 2. Решта рядків підраховуються за правилом двох перпендикулярів. Тобто кожен елемент нової таблиці дорівнює різниці між відповідними елементами вихідної таблиці і твором елементів, опиняються в основі перпендикулярів опущених зі старого елемента на ключовий стовпець і ключову рядок. p align="justify"> Так продовжуємо до тих пір, поки, всі елементи індексного рядка не негативні (позитивні і нулі).
Таблиця № 3
Базісиx0x1x2x3x4x5Ключевое отношеніех32 2/30012 1/32 2/31х22 2/30101/3-1/3-8х11 1/3100-1/3-2/3-2f6 2/30001/3-1 1/3