Линейное программирование. Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными

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

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

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

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

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

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

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

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

В общем виде задача линейного программирования (ЗЛП) может быть сформулирована как задача нахождения наибольшего (или наименьшего) значения линейной функции:

(3.1.1)

на некотором множестве , где удовлетворяют системе ограничений:

(3.1.2)

и, возможно, ограничениям:

. (3.1.3)

He умаляя общности, можно считать, что в системе (3.1.2) первые ограничений являются неравенствами, а последующие – уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (3.1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).

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

эквивалентна задаче поиска минимума функции

Задачу линейного программирования, записанную в форме (3.1.1) – (3.1.3), называют общей задачей линейного программирования.

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

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

Оптимальным решением или оптимальным планом ЗЛП называется решение системы ограничений (3.1.2), удовлетворяющее условиям (3.1.3), при котором линейная функция (3.1.1) принимает оптимальное (максимальное или минимальное значение).

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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) , при котором линейная функция

принимает максимальное или минимальное значение при ограничениях:

, ,

, ,

– целые числа.

3.1.1. Задача планирования производства

Задача планирования производства (или задача об использовании ресурсов) является одной из разновидностей задачи линейного программирования.

Рассмотрим пример подобной задачи.

Для изготовления двух видов продукции и используют четыре вида ресурсов , , и . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в табл.1 (цифры условные).

Таблица 1

Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		–
			–

Прибыль, получаемая от единицы продукции и , – соответственно 2 и 3 руб.

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Решение. Составим экономико-математическую модель задачи.

Обозначим , – число единиц продукции соответственно и , запланированных к производству. Для их изготовления потребуется единиц ресурса , единиц ресурса , единиц ресурса и единиц ресурса . Так как потребление ресурсов , , и не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

(3.1.4)

По смыслу задачи переменные

(3.1.5)

Суммарная прибыль составит руб. от реализации продукции и руб.– от реализации продукции , т.е.

. (3.1.6)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (3.1.4) и условию (3.1.5), при котором функция (3.1.6) принимает максимальное значение.

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

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

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

и условию при котором функция принимает максимальное значение.

Поиск по сайту: