Огляд задач комбінаторної оптимізації визначення рентабельності сільськогосподарського виробництва та методи їх розв’язування

Анотація

У роботі представлено огляд робіт полтавських дослідників присвячених математичному моделюванню задач на евклідових комбінаторних множинах. Викладено постановки практичних задач сільськогосподарського виробництва, а саме: задачі про забезпечення максимальної рентабельності виробництва; задачі про порядок засівання ділянок для отримання максимальної прибутковості; задачі про порядок засівання частини ділянок для максимального прибутку з урахуванням внесення добрив; задачі на знаходження оптимальних обсягів вирощування культур двома господарствами (різні модифікації). Побудовано моделі цих задач у вигляді задач евклідової комбінаторної оптимізації. Математична модель задачі про забезпечення максимальної рентабельності виробництва зводиться до умовної задачі з дробово-лінійною цільовою функцією на множині розміщень. Задача про порядок засівання ділянок для отримання максимальної прибутковості інтерпретована як повністю комбінаторна задача на множині переставлень. Для задачі про порядок засівання частини ділянок для максимального прибутку з урахуванням внесення добрив побудовано модель у вигляді частково комбінаторної задачі на переставній множині. Задачі на знаходження оптимальних обсягів вирощування культур двома господарствами розглядаються як задачі комбінаторної оптимізації ігрового типу з обмеженнями, що задають множину переставлень. Для розглянутих класів задач розроблено методи їх розв’язування. Для умовної задачі з дробово-лінійною цільовою функцією на комбінаторній множині розміщень запропоновано лінеаризацію функції та подальше застосування методу комбінаторного відсікання. Для умовних задач на вершинно розташованих множинах побудовано алгоритм комбінаторного відсікання, як для повністю, так і для частково комбінаторних задач, та модифікований метод гілок та меж. Задачі ігрового типу на переставних множинах розв’язуються різними ітераційними методами. Для всіх типів задач проведено числові експерименти, що підтвердили ефективність алгоритмів та швидкодію.