ЛІНІЙНЕ ПРОГРАМУВАННЯ: ДЛЯ ЧОГО ЦЕ, МОДЕЛІ, ОБМЕЖЕННЯ, ПРОГРАМИ - МАТЕМАТИКА - 2025

Лінійне програмування являє собою математичний метод , який буде використовуватися для оптимізації (максимізувати або мінімізувати в залежності від обставин) , в функції якого змінні обмежені, а поки функція і обмеження є лінійно залежними змінними.

Взагалі, функція оптимізації моделює практичну ситуацію, таку як прибуток виробника, чиї вкладення праці, робочої сили чи обладнання обмежені.

Малюнок 1. Лінійне програмування широко використовується для оптимізації прибутку. Джерело: Piqsels.

Один з найпростіших випадків - це максимізація лінійної функції, яка залежить лише від двох змінних, званих змінними рішення. Він може мати форму:

Z = k ₁ x + k ₂ y

При k ₁ і k ₂ постійна. Ця функція відома як об'єктивна функція. Звичайно, є ситуації, які заслуговують більше двох змінних для вивчення, будучи складнішими:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

А обмеження також математично моделюються системою рівнянь чи нерівностей, однаково лінійних у x та y.

Сукупність рішень у цій системі називається можливими рішеннями або можливими точками. І серед можливих моментів є хоча б один, який оптимізує цільову функцію.

Лінійне програмування було самостійно розроблено американським фізиком і математиком Джорджем Данцигом (1914-2005) та російським математиком і економістом Леонідом Канторовичем (1912-1986) незабаром після Другої світової війни.

Метод вирішення проблем, відомий як симплексний метод, - це дітище Данцига, який працював у ВПС США, Беркліському університеті та Стенфордському університеті.

Малюнок 2. Математики Георгій Данциг (ліворуч) та Леонід Канторович (праворуч). Джерело: Ф. Сапата.

Моделі лінійного програмування

Елементами, необхідними для встановлення лінійної моделі програмування, придатної для практичної ситуації, є:

-Об’єктивна функція

-Різні змінні

-Обмеження

У цільовій функції ви визначаєте, чого хочете досягти. Наприклад, припустимо, ви хочете отримати максимальний прибуток від виробництва певної продукції. Тоді встановлюється функція «прибуток», відповідно до ціни, за якою продається продукція.

У математичному плані цю функцію можна виразити скороченим, використовуючи позначення підсумовування:

Z = ∑k _i x _i

У цьому рівнянні k _i - коефіцієнти, а x _i - змінні рішення.

Змінні рішення - це елементи системи, контроль якої був, а їх значення - додатні реальні числа. У запропонованому прикладі змінними рішення є кількість кожного продукту, який буде виготовлений для отримання максимального прибутку.

Нарешті, ми маємо обмеження, які є лінійними рівняннями або нерівностями з точки зору змінних рішень. Вони описують обмеження проблеми, які відомі і можуть бути, наприклад, кількістю сировини, наявної у виробництві.

Види обмежень

Ви можете мати число обмежень M, починаючи від j = 1 до j = M. Математично обмеження бувають трьох типів:

1. A _j = ∑ a _ij . х _i
2. B _j ≥ ∑ b _ij . х _i
3. C _j ≤ ∑ c _ij . х _i

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

Два решти обмежень є лінійними нерівностями, і це означає, що відомі значення B _j і C _j можуть бути дотримані або перевищені, коли символ, що з'являється, ≥ (більший або рівний) або поважається або не перевищується, якщо символ ≤ (менше або рівне).

Приклад моделі

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

Місцева кондитерська відома двома спеціальностями: чорний лісовий пиріг та торт з куркою.

При його приготуванні їм потрібні яйця і цукор. Для чорного лісу потрібно 9 яєць і 500 г цукру, тоді як для сарфантину потрібно 8 яєць і 800 г цукру. Відповідні ціни продажу складають 8 та 10 доларів.

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

Змінні рішення

Змінні рішення - "x" і "y", які приймають реальні значення:

-x: кількість чорних лісових пирогів

-y: торти жертовного типу.

Обмеження

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

Тому в математичній формі ці обмеження приймають форму:

1. x ≥ 0
2. і ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Обмеження 1 і 2 складають умову негативу, раніше викритого, і всі підняті нерівності є лінійними. У обмеженнях 3 та 4 є значення, які не повинні перевищувати: 144 яйця та 10 кг цукру.

Об'єктивна функція

Нарешті, цільовою функцією є прибуток, отриманий при виробництві «х» кількості чорних лісових пирогів плюс «у» кількості сарфантинів. Він будується шляхом множення ціни на кількість виготовлених тортів і додавання для кожного виду. Це лінійна функція, яку ми будемо називати G (x, y):

G = 8x + 10y

Методи рішення

До різних методологій рішення можна віднести графічні методи, алгоритм симплекс та метод внутрішніх точок.

- Графічний або геометричний метод

Коли у вас є двовимірна проблема, подібна до попереднього розділу, обмеження визначають полігональну область в площині xy, яку називають можливою областю або областю життєздатності.

Малюнок 3. Доцільна область, де знайдено рішення задачі оптимізації. Джерело: Wikimedia Commons.

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

Що стосується пекарні, яка хоче оптимізувати прибуток, то обмежувальні лінії:

1. x = 0
2. y = 0
3. 9x + 8y = 144
4. 0,5 x + 0,8y = 10

Усі точки в регіоні, замкнені цими рядками, є можливими рішеннями, тому їх нескінченно багато. За винятком випадків, коли здійсненна область виявляється порожньою, в цьому випадку поставлена ​​проблема не має рішення.

На щастя, для проблеми з випічкою здійсненна область не порожня, ми маємо її нижче.

Малюнок 4. Доцільна область проблеми випічки. Рядок із коефіцієнтом посилення 0 перетинає початок. Джерело: Ф. Сапата з Геогебра.

Оптимальне рішення, якщо воно існує, знаходить за допомогою цільової функції. Наприклад, намагаючись знайти максимальний прибуток G, ми маємо такий рядок, який називається лінією прибутку:

G = k ₁ x + k ₂ y → y = -k ₁ x / k ₂ + G / k ₂

За допомогою цього рядка ми отримуємо всі пари (x, y), які забезпечують задане посилення G, тому існує сімейство ліній відповідно до значення G, але всі з однаковим нахилом -k ₁ / k ₂ , тому вони паралельні лінії.

Оптимальне рішення

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

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

Для нашого тіста вершинами-кандидатами є A, B і C.

- симплексний метод Данцига

Графічний або геометричний метод застосовний для двох змінних. Однак це складніше, коли є три змінні, і неможливо їх використовувати для більшої кількості змінних.

При вирішенні проблем з більш ніж двома змінними використовується симплекс-метод, який складається з серії алгоритмів для оптимізації цільових функцій. Для проведення обчислень часто використовують матриці та просту арифметику.

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

Програми

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

Ось кілька полів:

-У маркетингу використовується для пошуку найкращого поєднання засобів масової інформації (соціальні мережі, телебачення, преса та інші) для реклами певного товару.

-Для призначення адекватних завдань персоналу компанії чи фабрики або графіків до них.

-У підборі найпоживніших продуктів харчування та з найнижчою вартістю у тваринництві та птахівництві.

Розв’язані вправи

- Вправа 1

Графічно вирішити модель лінійного програмування, підняту в попередніх розділах.

Рішення

Необхідно графікувати набір значень, визначених системою обмежень, зазначених у задачі:

1. x ≥ 0
2. і ≥0
3. 9x + 8y ≤ 144
4. 0,5 x + 0,8y ≤ 10

Область, задана нерівностями 1 і 2, відповідає першому квадрату декартової площини. Щодо нерівностей 3 і 4, ми почнемо з пошуку рядків обмеження:

9x + 8y = 144

0,5 x + 0,8y = 10 → 5x + 8y = 100

Доцільна область - це чотирикутник, вершинами якого є точки A, B, C і D.

Мінімальний прибуток дорівнює 0, тому рядок 8x + 10y = 0 є нижньою межею, а лінії з метою отримання прибутку мають нахил -8/10 = - 0,8.

Ця величина відрізняється від схилів інших ліній обмеження і оскільки обмежувальна область обмежена, існує унікальне рішення.

Малюнок 5. Графічне рішення вправи 1, що показує можливу область та точку розчину C в одній з вершин зазначеної області. Джерело: Ф. Сапата.

Це рішення відповідає лінії нахилу -0,8, яка проходить через будь-яку з точок A, B або C, координати яких:

А (11; 5.625)

B (0; 12,5)

C (16, 0)

Оптимальне рішення

Обчислюємо значення G для кожної з цих точок:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12,5): G _B = 8 x 0 + 10 x 12,5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

Найбільший прибуток здобуває виготовлення 11 чорних лісових пирогів та 5625 пиріжкових коржів. Це рішення узгоджується з рішенням, знайденим через програмне забезпечення.

- Вправа 2

Перевірте результат попередньої вправи, використовуючи функцію Solver, доступну в більшості електронних таблиць, таких як Excel або LibreOffice Calc, які включають алгоритм Simplex для оптимізації в лінійному програмуванні.

Рішення

Малюнок 6. Деталізація рішення з вправи 1 через електронну таблицю Libre Office Calc. Джерело: Ф. Сапата.

Малюнок 7. Деталізація рішення з вправи 1 через електронну таблицю Libre Office Calc. Джерело: Ф. Сапата.

Список літератури

1. Блискуча. Лінійне програмування. Відновлено з сайту: британський.org.
2. Еппен, Г. 2000. Операційні дослідження в галузі адміністративної науки. 5-й. Видання. Prentice Hall.
3. Хеусслер, Е. 1992. Математика для управління та економіки. 2-й. Видання. Grupo Редакція Iberoamericana.
4. Hiru.eus. Лінійне програмування. Відновлено з: hiru.eus.
5. Вікіпедія. Лінійне програмування. Відновлено: es. wikipedia.org.