2 ; А 3 знаходиться 200; 450; 250 одиниць вантажу відповідно, який треба доставити в пункти В 1 ; В 2 ; В 3 ; В 4 ; В 5 в кількості 100; 125; 325; 250; 100 відповідно. Відстань між пунктами задано в кілометрах наступній матрицею:
В
Потрібно знайти оптимальний план закріплення споживачів за постачальниками однорідного вантажу за умови мінімізації загального пробігу автомобілів. Розглянути два методи отримання початкового плану. br/>
1. Графічний метод розв'язання задачі лінійного програмування
В В
Побудуємо прямі обмежень, для чого обчислимо координати точок перетину цих прямих з осями координат. З умов обмеження отримаємо область допустимих значень G
В
Малюнок 1. Графічний метод розв'язання задачі лінійного програмування. p align="justify"> Напрям зростання цільової функції зазначено на малюнку 1. Відповідно, точкою максимуму є точка D. Знайдемо її координати виходячи з того, що вона є точкою перетину графіків (1) і (2). Для цього вирішимо систему рівнянь:
В
Рішенням цієї системи рівнянь будуть координати точки D: x1 = 6, x2 = 8. Підставляючи ці значення в цільову функцію, отримаємо остаточну відповідь:. br/>
. Рішення задачі лінійного програмування симплекс-методом
В В
Запишемо задачу в канонічній формі як того вимагає симплекс-метод, для цього введемо дві змінні y 4 і y 5 , отримаємо:
В В
У вийшла системі відсутні базисні змінні, тому в перше і друге рівняння додаємо штучні змінні y 6 і y 7 . Щоб можна було застосувати симплекс-метод система рівнянь-обмежень повинна бути системою з базисом, тобто в кожному рівнянні повинна бути змінна з коефіцієнтом 1, яка входить тільки в одне рівняння системи, в нашому випадку це y 6 і y 7. Отримуємо, так звану, М-задачу:
В
= (0, 0, 0, 0, 0, 2, 3) T
Дана система є системою з базисом, отже, для вирішення можна застосувати симплекс-метод. Запишемо початкову сим...
