Як почати працювати в ІТ

Виконання завдань по роботі в ІТ галузі.

Project maintained by BobasB Hosted on GitHub Pages — Theme by mattgraham

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

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

Загальна ідея методу

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

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

Загальна математична модель

Задача лінійного програмування має наступний вигляд:
[ \text{Maximize or Minimize } \quad Z = c_1x_1 + c_2x_2 + \dots + c_nx_n ] за умов:
[ a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1 ] [ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \leq b_2 ] [ \dots ] [ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n \leq b_m ] та ( x_1, x_2, \dots, x_n \geq 0 ).

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

Будь-яка задача ЛП складається з трьох ключових елементів:

  1. Цільова функція
    • Це математичний вираз, який потрібно максимізувати або мінімізувати.
    • Зазвичай цільова функція є лінійною та має вигляд:
      [ Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n ]
    • Де:
      • ( Z ) — значення функції (наприклад, прибуток, витрати, ефективність).
      • ( x_1, x_2, …, x_n ) — змінні (наприклад, кількість товару, використані ресурси).
      • ( c_1, c_2, …, c_n ) — коефіцієнти (наприклад, дохід на одиницю товару, витрати).
  2. Обмеження (система нерівностей)
    • Описують допустимі значення змінних, наприклад, кількість ресурсів, потужність виробництва.
    • Мають вигляд лінійних нерівностей або рівнянь:
      [ a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \leq b_1 ] [ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \leq b_2 ]
    • Де:
      • ( a_{ij} ) — коефіцієнти обмежень.
      • ( b_1, b_2, …, b_m ) — доступні ресурси.
  3. Обмеження на змінні (області допустимих рішень)
    • Найчастіше обмеження на змінні мають вигляд: [ x_1, x_2, …, x_n \geq 0 ]
    • Це означає, що змінні не можуть бути від’ємними (наприклад, немає сенсу виробляти від’ємну кількість товару).

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

Щоб правильно сформулювати задачу ЛП, потрібно виконати наступні кроки:

  1. Визначити змінні
    • Позначити величини, які потрібно знайти (наприклад, кількість товару, ресурсів, часу).
    • Наприклад, якщо потрібно вирішити, скільки продуктів виробляти, введемо змінні ( x ) і ( y ) — кількість двох видів продукції.
  2. Записати цільову функцію
    • Визначити величину, яку потрібно оптимізувати (прибуток, витрати, час, продуктивність).
    • Наприклад, якщо підприємство отримує прибуток 50 грн за одиницю товару ( x ) і 80 грн за одиницю товару ( y ), то: [ Z = 50x + 80y \quad \text{(максимізація прибутку)} ]
  3. Записати обмеження
    • Врахувати всі наявні ресурси та їхні обмеження.
    • Наприклад, якщо виробництво обмежене 100 годинами роботи та 120 кг сировини:
      • Товар ( x ) потребує 2 години і 3 кг сировини.
      • Товар ( y ) потребує 4 години і 2 кг сировини. [ 2x + 4y \leq 100 \quad \text{(обмеження за часом)} ] [ 3x + 2y \leq 120 \quad \text{(обмеження за сировиною)} ]
  4. Записати умови невід’ємності змінних
    [ x, y \geq 0 ]

Геометрична інтерпретація методу

Графічний метод ЛП підходить для задач із двома змінними.

  1. Будується координатна площина з осями ( x ) та ( y ).
  2. Будуються лінії обмежень, що розділяють площину на допустимі та недопустимі області.
  3. Область, що задовольняє всі обмеження, називається допустимою.
  4. Оптимальне рішення знаходиться в одній із вершин цієї області.

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

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

Існує кілька методів розв’язання задач ЛП:

  1. Графічний метод
    • Використовується для задач із двома змінними.
    • Всі обмеження зображаються як прямі на площині, а оптимальне рішення — у вершині допустимої області.
  2. Симплекс-метод
    • Ефективний для багатовимірних задач.
    • Побудований на ітераційному переході між вершинами багатогранника допустимих рішень.
  3. Методи внутрішніх точок
    • Використовуються для великих задач.
    • Оптимальне рішення шукається всередині області допустимих значень.

Виконання роботи

  1. :star: Виконайте всі приклади наведені у Пайтон Ноутбуках. Спробуйте змінити вхідні дані та поекспериментувати яким буде розвязок.

Здача роботи