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

Понятие линейного программирования

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

Одним из первых и наиболее подробно изученных разделов математического программирования является линейное программирование. Линейное программирование применимо для построения математических моделей процессов, в основу которых может быть положена гипотеза линейного представления реального мира, то есть экономических задач, задач управления и планирования, оптимального размещения оборудования и товаров и так далее.

К задачам линейного программирования относятся такие задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств и неравенств.

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования относятся следующие задачи: задача о диете; транспортная задача; модель рационального использования посевных площадей; составление плана производства; динамическая модель планирования; модель рационального использования трудовых ресурсов; расчет химической технологии и так далее.

В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения.

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

В обществе протекают сложные экономические процессы, которые зависят от множества разнообразных факторов: политических, социальных, экономических и других. Исследование экономических процессов, анализ их развития, весьма затруднен, так как требует учета и переработки большого объема информации.

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

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

Экономико-математическая модель — это концентрированное выражение существенных взаимосвязей и закономерностей процесса в математической форме.

Математическая модель представляет собой уравнение или систему уравнений и неравенств, описывающую взаимосвязи, происходящие в оригинале. Запись процессов через систему ограничений с использованием буквенных символов имеют следующий вид:? a_ij x_ij B_i

Решение системы неравенств и уравнений имеет цель — найти наилучшие значения параметров системы, то есть цель моделирования — поиск наилучших решений. Математически это означает решение задач на экстремум (max, min.) функции цели.

Функция цели имеет вид: F=?c_jx_j>max (min).

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

Если ограничения (система уравнений и неравенств) и целевая функция представлены переменными (Х₁, Х₂,…Хn) в первой степени, т. е. линейны, возникает задача линейного программирования. Если имеет место хотя бы одно нелинейное выражение, то задача относится к нелинейному программированию.

Задачи линейного программирования решаются с применением алгоритмов симплексного и распределительного методов.

Использование экономико-математических моделей возможно при условиях:

• — ограниченности ресурсов;
• — неоднозначности (многовариантности) получаемых решений;
• — наличия единой целевой функции.

Как правило, землеустроительные и кадастровые задачи имеют многовариантный, альтернативный характер. Вопрос состоит в том, как из множества допустимых вариантов выбрать оптимальный по заданному критерию.

Поэтому наиболее разработанными и хорошо апробированными в практике землеустройства и кадастра являются экономико-математические модели, реализуемые с помощью методов линейного программирования.