Контрольная работа: Розв’язання лінійних задач методами лінійного програмування

Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.

Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х₃ , х₄ і х₅ . Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х₆ і х₇ та отримаємо одиничні матриці А₆ і А₇ . Де

і

В результаті наведених перетворень отримаємо наступну задачу:

У виразі функції величину М вважаємо достатньо великим додатнім числом, оскільки задача розв’язується на знаходження мінімального значення функції.

Запишемо задачу у векторній формі:

де

В якості базису вибираємо одиничні вектори А₆ , А₄ , А₇ . Вільні невідомі прирівнюємо нулю . В результаті отримаємо початковий опорний план розширеної задачі

,

якому відповідає розкладення

Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції і оцінок Маємо:

тобто оскільки М попередньо не фіксовано, то оцінки є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежний від М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівняти оцінки між собою. Для векторів базису оцінки дорівнюють нулю.

Таблиця1– Перша симплексна таблиця

Базис	С базису	А0
			х1	х2	х3	х4	х5	х6	х7
х6	М	8	1		-1	0	0	1	0
х4	0	20	3	4	0	1	0	0	0
х7	М	6	3	1	0	0	-1	0	1
F-C	–	0	-5	-2	0	0	0	0	0
М	–	14	4	4	-1	0	-1	0	0

В (М) рядку є додатні оцінки, тому опорний план Х₀ не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне С_j . Розв’язувальним рядком вибирається той, в якому найменше відношення Серед коефіцієнтів розкладання векторів А₁ і А₂ по базису є додатні, тому хоча б один з векторів існує.. Знайдемо ці значення:

;

Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А₂ включаємо в базис, а вектор А₆ виключаємо з нього.

Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.

Таблиця2– Друга симплексна таблиця

Базис	С базису	А0
			х1	х2	х3	х4	х5	х6	х7
х2	2	2,67	0,33	1	-0,33	0	0	0,33	0
х4	0	9,33	1,67	0	1,33	1	0	-1,33	0
х7	М	3,33		0	0,33	0	-1	-0,33	1
F-C	–	5,33	-4,33	0	-0,67	0	0	0,67	0
М	–	3,33	2,67	0	0,33	0	-1	-1,33	0

В (М) рядку є додатні оцінки, тому план, зображений в таблиці2 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Тобто за розв’язувальний стовпчик вибираємо перший. Мінімальне відношення