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

Общая задача линейного программирования состоит в нахождении максимума (минимума) линейной функции

 (1)

при ограничениях

(2)

Функция  называется функцией цели или целевой функцией.

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

Многие социально-экономические процессы можно описать в виде математических символов и чисел. Процедура описания социально-экономического процесса в математическую форму – это построение экономико-математической модели задачи.

Этапы построения экономико-математической модели задачи:

1) определить переменные и обозначить их , ,… ,

2) определить цель задачи и составить целевую функцию,

3) определить условия достижения цели и записать ограничения.

При определении переменных обязательно нужно указывать единицы измерения.

Пример 1. Построить экономико-математическую модель задачи. Два предприятия МУП «Чистота» и МУП «Блеск» занимаются уборкой дорог (проезжей части) города. Максимальная протяженность дорог, которую необходимо убрать в сутки этим предприятиям составляет 372 км. У обоих предприятий есть три вида техники, задействованной в уборке. Лимиты выполнения работ по каждому виду техники и стоимость выполнения уборки представлены в таблице.

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

Решение

1) В данной задаче речь идет об оптимальном объеме уборочных работ предприятиями, обеспечивающем минимальную стоимость работ, оплачиваемую из муниципального бюджета. Другими словами, нужно определить, какую протяженность дорог каждое предприятия должно убрать, чтобы для бюджета затраты были минимальные, а дороги были убраны в полном объеме.

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

- протяженность дорог, убранное предприятием МУП «Чистота», км,

- протяженность дорог, убранное предприятием МУП «Блеск», км.

2) Целью задачи является минимальная стоимость уборочных работ. Стоимость работ складывается исходя из стоимости единицы объема работ и выполненного объема работ.

В нашем случае, стоимость единицы объема работ указана в таблице и составляет 1 тыс. руб. для МУП «Чистота» и 1,1 тыс. руб. для МУП «Блеск». Объемом выполненных работ является протяженность убранных дорог, который составляет км для МУП «Чистота» и  км для МУП «Блеск». Следовательно, стоимость объема выполненных работ МУП «Чистота» составит произведение стоимости единицы объема работа и объема выполненных работ, то есть =  (тыс. руб.), а стоимость объема выполненных работ МУП «Блеск» =  (тыс. руб.). Общая стоимость уборочных работ для муниципального бюджета составит сумму стоимости объемов выполненных работ МУП «Чистота» и МУП «Блеск», то есть  (тыс. руб.). Так как целью задачи является минимум затрат, то целевая функция будет иметь вид:

.

3)Определим условия достижения цели. В задаче сказано, что протяженность дорог, которые необходимо убрать составляет 372 км, следовательно, первым ограничением будет равенство, указывающее на то, что оба предприятия в сумме должны убрать 372 км. На первом этапе мы определили, что протяженность дорог, убранных МУП «Чистота» составит  км, а протяженность дорог, убранных МУП «Блеск» составит  км, следовательно, вместе они уберут ) км. Поэтому первое ограничение в экономико-математической модели задачи примет вид:

=372 – ограничение по протяженности дорог, которые необходимо убрать.

Помимо протяженности в условии задачи указаны лимиты времени работы каждого вида техники в сутки и скорость их работы. На каждом предприятии имеется три вида техники, которые производят уборку с разной скоростью. Первый вид техники может работать не более 10 часов, второй вид – не более 12 часов, третий – не более 14 часов. Определим по каждому виду техники количество часов, затрачиваемое на выполнение запланированного объема работ.

Техника 1 вида:  часов (МУП «Чистота»),  часов (МУП «Блеск»). В сумме их работа составит часов. Отсюда ограничение по работе техники первого вида примет вид:

.

Аналогично составляем ограничения по работе техники второго и третьего видов:

,

.

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

Теперь составим экономико-математическую модель задачи:

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

Практическое занятие 3

Выучить определения и этапы построения экономико-математической модели задачи.

Решите задачи.

1. Постройте экономико-математическую модель определения суточного рациона, содержащего не менее суточной потребности человека в необходимых питательных веществах и обеспечивающего минимальную общую стоимость продуктов. Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг имеющихся в магазине продуктов питания, а также их стоимость приведены в таблице:

Построить экономико-математическую модель задачи.

2. Построить экономико-математическую модель для определения оптимального плана объемов перевозок по следующим условиям. На четырех складах имеется продукция в количестве: А₁=200, А₂=300, А₃=250, А₄=180. Для пяти магазинов требуется продукция в количестве: В₁=150, В₂=100, В₃=200, В₄=220, В₅=210. Стоимость перевозок единицы продукции из i-го склада в j-ый магазин представлены в виде матрицы: .

Домашнее задание:

На складах А₁, А₂, А₃ имеются запасы цемента в 170, 320, 260 тонн соответственно. Получатели груза В₁, В₂, В₃ соответственно должны получить товары в количествах 290, 360 и 100 тонн соответственно. Найти такой вариант перевозки груза, при котором сумма затрат будет минимальной. Расходы перевозки в таблице:

Построить экономико-математическую модель задачи.