Геометрична постановка задачі лінійного програмування

Задача 1. Прибуток від виробництва і реалізації одиниці товару 1 становить е₁ = 2 грн., товару 2 відповідно е₂ = 5 грн. Підприємство володіє трьома видами ресурсів:

- А = 400 кг і використовується на виробництво товару 1;

- Б = 300 кг і використовується на виробництво товару 2;

- В = 500 кг і використовується на виробництво товарів 1 та 2 (в однакових кількостях).

Скласти план виробництва для досягнення максимальної прибутковості.

х₁ ≤ 400, х₁ ≥ 0

х₂ ≤ 300, х₂ ≥ 0

х₁ + х₂ ≤ 500

max f = 2x₁ + 5x₂

Максимальний прибуток досягається при х₁=200 та

х₂ = 300, а саме 2×200 + 5×300 = 1900

ТРАНСПОРТНА ЗАДАЧА

Нехай m постачальників має однорідну продукцію А₁, А₂, …, А_m. Продукцію необхідно доставити n споживачам у кількостях В₁, В₂, …, В_n. Усі відстані від постачальників i (i= 1, 2, …, n) до споживачів j (j = 1, 2, …, m) C_ij відомі, C_ij може означати також тариф перевезення від постачальника до споживача. Будь-який покупець може отримати товар від будь-якого постачальника. В цих умовах треба скласти план перевезень, щоб загальний вантажообіг був мінімальним.

–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––

Задача 2. Потрібно перевезти однорідні товари від 2-х постачальників: Львівського та Київського чотирьом гуртівням (А, B, C, D). Дано відстані від виробників до покупців (у сотнях км), запаси товару у виробників та потреби покупців. Розрахувати найменший план перевезень (у тонно-кілометрах).

Цільова функція: min f = 17х₁₁ + 26х₁₂ + 28х₁₃ + 27х₁₄ + 16х₂₁ + 22х₂₂ + 26х₂₃ + 21х₂₄

Обмеження: х₁₁ + х₁₂ + х₁₃ + х₁₄ = 13

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 17

х₁₁ + х₂₁ = 12

х₁₂ + х₂₂ = 10

х₁₃ + х₂₃ = 6

х₁₄ + х₂₄ = 2

Число обмежень має бути рівним m + n – 1 (у нашому випадку 2 + 4 – 1 = 5), тому якесь з обмежень можна виключити (наприклад, перше).