Приклад. Поняття про задачі лінійного програмування

Поняття про задачі лінійного програмування

Почнемо з розгляду однієї простої задачі про перевезення хліба.

Приклад.

Для постачання 3-х районів міста хлібом є 2 хлібозаводи. 1-й район щодня споживає хліба 26 т., 2-й - 14 т., 3-й - 10 т. Хлібозавод № 1 випікає щодня 30 т. Хліба, а завод № 2 - 20 т. Вартість у рублях доставки однієї тонни хліба з кожного хлібозаводу кожному району наведена в таблиці:

Хлібозавод	Район
№ 1 № 2

Потрібно скласти найбільш ощадливий план (програму) перевезення хліба.

Позначимо через число тонн хліба, що буде перевозитися із хлібозаводу № 1 у перший район, а через - число тонн хліба, що буде перевозитися із цього хлібозаводу в другий район.

Тоді в третій район із хлібозаводу № 1 буде перевозитися - тонн.

Тому що перший район щодня споживає 26 тонн хліба, те 26 - тонн потрібно доставляти із хлібозаводу № 2.

Аналогічно із хлібозаводу № 2 потрібно доставляти другому району 14- , а третьому району тонн хліба.

Отже, щоденний план перевезень хліба можна представити таблицею:

Хлібозавод	Район
№ 1 № 2

Легко бачити, що вартість S всього перевезення дорівнює сумі попарних добутків чисел з першої таблиці на відповідні числа другої таблиці:

, тобто

.

Так як кількість хліба, що привозять в даний район міста, не може бути відємною, то всі числа другої таблиці повинні бути ненегативними:

Вартість S можна розглядати як функцію точки М, координати якої задовольняють нерівностям (2). Множина всіх таких точок є багатокутником АВCDЕ. Функцію S називають цільовою функцією.

Покажемо, що цільова функція S своє найменше значення приймає в одній з вершин багатокутника ABCDE.

Нехай функція S приймає значення c у деякій точці М багатокутника ABCDE. Очевидно, що це ж значення вона приймає у всіх точках прямій l, заданої рівнянням

Зокрема, вартість S дорівнює c у точках перетину прямій l із границею багатокутника ABCDE.

C (26; 4)

χ

E (20; 0) D (26; 0)

Очевидно, що якщо при деякому значенні с пряма (3) проходить через внутрішні точки багатокутника ABCDE., те й будь-яка пряма, задана рівнянням

,

при досить малому 0 також проходить через внутрішні точки багатокутника ABCDE. Тому таке значення функції S не може бути мінімальним, і, отже, найменше значення вона приймає на прямих, заданих рівнянням виду (3), які перетинаються тільки із границею багатокутника ABCDE.

Легко бачити, що будь-яка пряма, що перетинається тільки із границею багатокутника, обов'язково проходить через його вершину. Звідси треба, що цільова функція S приймає найменше значення в одній з вершин багатокутника ABCDE.

Знайдемо тепер значення S у кожній з вершин багатокутника ABCDE:

Звідси видно, що найменше значення S дорівнює 154 і приймається в точці В, тобто при

Таким чином, самий ощадливий план (сама ощадлива програма) перевезення хліба задається наступною таблицею:

Хлібозавод	Район
№ 1 № 2

---

Дата добавления: 2015-07-11