logo
СПР Олонина

Решение экономико-математических задач методами линейного программирования

Наиболее разработанными, хорошо апробированными и распространенными в практике землеустройства являются экономико-математические модели, реализуемые с использованием методов линейного программирования. В моделях этого класса целевая функция и условия (ограничения) задачи представлены в виде системы линейных уравнений и неравенств ( в которых все неизвестные только в первой степени).

Землеустроительные задачи, решаемые методами линейного программирования, должны обязательно удовлетворять следующим требованиям:

Следовательно, линейное программирование представляет собой часть математического программирования, связанную с решением экстремальных задач, в которых целевая функция установка (критерий оптимальности) и условия (ограничения) выражаются линейными функциями.

Для решения задач линейного программирования разработан ряд алгоритмов, наиболее известные из которых – алгоритмы симплексного метода и распределительного метода. Все они базируются на последовательном улучшении некоторого первоначального плана и за определенное число циклических повторяющихся вычислений (итераций) позволяют получить оптимальное решение. После каждой из итераций значение целевой функции улучшается. Процесс повторяется до тех пор, пока не будет достигнут оптимальный план. Существуют простые критерии, позволяющие на каждой стадии процесса, проверить, является ли вновь полученный план оптимальным. Если оптимум не достигнут, то цикл вычислений повторяют.

Симплекс-метод универсален в том смысле, что позволяет решать задачи, условия которых выражены в различных единицах измерения.

Распределительный метод является специальной разновидностью симплекс-метода, применяемой к любому случаю, где речь идет о распределении определенного количества однородного ресурса между потребителями. Алгоритм распределительного метода также позволяет, начиная с произвольного исходного плана, за определенное число операций получить оптимальное решении задачи (оптимальный план). Он также предполагает проверку оптимальности на каждой итерации, и если решение не достигнуто, вычисления продолжаются.

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