- •Міністерство освіти і науки України
- •Математичні моделі економічних задач
- •1.1. Задача планування виробництва
- •1.2. Задача складання раціону (задача про дієту, задача про суміші)
- •1.3. Транспортна задача
- •1.4. Задача про мінімізацію відходів
- •К 2ількість шматків
- •1.5. Задача про призначення
- •Загальна постановка задач лінійного програмування (лп)
- •Перелік питань для самоперевірки
- •Лекція 2
- •Тема 2. Геометрична інтерпретація задач лінійного програмування. Задача лінійного програмування, форми її запису
- •Приведення задачі лп до канонічного виду
- •Приведення задачі лп до симетричного виду
- •Перелік питань для самоперевірки
- •3.1. Визначення вихідного опорного плану
- •3.2. Симплексні таблиці
- •3.3. Поняття про м-метод
- •Перелік питань для самоперевірки
- •Лекція 4
- •Тема 4. Двоїстість у лінійному програмуванні
- •Перелік питань для самоперевірки
- •Лекція 5
- •Тема 5. Методика розв’язування транспортної задачі
- •5.1. Приведення задачі до замкненої форми
- •5.2. Визначення вихідного опорного плану
- •5.3. Метод потенціалів
- •Перелік питань для самоперевірки
- •6.1. Метод відсікань Гоморі
- •Перелік питань для самоперевірки
- •Лекція 6
- •Тема 7. Елементи теорії ігор
- •7.1. Графічний метод
- •7.2. Приведення матричної гри до задачі лінійного програмування
- •Перелік питань для самоперевірки
- •8.2. Задачі нелінійного програмування з нелінійною цільовою функцією та лінійною системою обмежень
- •Перелік питань для самоперевірки
- •Лекція 8
- •Тема 9. Динамічне програмування
- •9.1. Задача про розподіл коштів між підприємствами
- •Рішення
- •9.2. Задача про заміну обладнання
- •Рішення
- •Перелік питань для самоперевірки
- •Список рекомендованої літератури
3.1. Визначення вихідного опорного плану
У наступному прикладі розглядається один з можливих алгоритмів одержання опорного плану.
Задача 3.1. Знайти вихідний опорний план для задачі
Рішення
Дана задача подана у канонічному виді. Побудуємо вихідний опорний план. З коефіцієнтів при змінних і вільних членах рівнянь системи обмежень складаємо розширену матрицю (її j-й стовпець відповідає вектору-стовпцю коефіцієнтів при змінній xj (j=1,2,3,4,5), останній стовпець – вектору-стовпцю вільних членів). Приводимо дану матрицю до одиничного базису (за допомогою елементарних перетворень рядків матриці виділяємо максимальну кількість попарно різних одиничних векторів-стовпців). Помножимо перший і четвертий рядки на (–1):
.
Змінні, яким відповідають одиничні вектори-стовпці у перетвореній матриці, будемо вважати базисними, інші змінні – вільними.
У нашому випадку
I крок. Базисні змінні: x3, x4, x5, x6; вільні змінні: x1, x2.
Тому базисний розв’язок (у силу його визначення): . Цей розв’язок не є допустимим, тому що він містить дві від’ємні компоненти (виділені).
Знаходимо новий базисний розв’язок. Визначаємо базисну змінну, що виводиться з базису, і вільну змінну, що вводиться замість неї до базису. Для цього розглянемо рядки матриці, де містяться від’ємні вільні члени і(перший і четвертий), і від’ємні коефіцієнти при вільних зміннихx1 і x2 у цих рядках: ,, . Знаходимо
Мінімум досягається на елементі . Цей елемент будеключовим. Його перший індекс визначає ключовий рядок IV (який вказує на базисну змінну x6, що виводиться з базису), другий індекс – ключовий стовпець II (змінну x2, що вводиться до базису). За допомогою елементарних перетворень рядків матриці в стовпці II будуємо одиничний вектор, в якому 1 знаходиться в рядку IV. (Помножимо рядок IV на (–1), одержимо . Потім додамо до рядка I рядок IV, помножений на 3, і віднімемо з рядків II і III рядок IV).
.
Після перетворення
II крок. Базисні змінні: x2, x3, x4, x5; вільні змінні: x1, x6.
Тому базисний розв’язок: . Цей розв’язок не є допустимим, тому що він теж містить від’ємну компоненту.
Знову виконуємо перетворення. Рядок I (з від’ємним вільним членом ) має від’ємні коефіцієнти при вільних зміннихx1 і x6 у цьому рядку: ,. Знаходимо
Мінімум відповідає елементу , тому базисною змінною, що виводиться з базису, єx3 (третій стовпець містить одиничний вектор, в якому 1 розташована у ключовому рядку I), вільною змінною, що вводиться до базису, є x6. За допомогою елементарних перетворень у стовпці VI будуємо одиничний вектор, в якому 1 розташована в рядку I.
.
Після другого перетворення
III крок. Базисні змінні: x2, x4, x5, x6. Вільні змінні: x1, x3.
Базисний розв’язок: . Цей розв’язок вже є опорним планом задачі, тому що всі його компоненти невід’ємні.
Зауваження 3.1. Якщо базисний розв’язок не є допустимим, а в рівнянні, що містить від’ємний вільний член, немає вільної змінної з від’ємним коефіцієнтом, то в цьому випадку опорний план одержати неможливо, тобто умови задачі суперечливі.