Сущность и использование транспортных задач

2. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ПРИ РЕШЕНИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

2.1 Понятие задачи линейного программирования

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Л.В. Канторовича «Математические методы организации и планирования производства» [2]. Поскольку методы, изложенные им, были мало пригодны для ручного

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

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

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

В этом случае говорят, что задача представлена в канонической форме. При этом система линейных уравнений и неравенств, определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности. В частном случае, если I = Ш, то система состоит только из линейных неравенств, а если I = M, то – из линейных уравнений.

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

1) показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2, ., xn);

2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

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

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

- выбор некоторого числа переменных величин, заданием числовых значений которых однозначно определяется одно из возможных состояний исследуемого объекта или явления;

- выражение взаимосвязей, присущих исследуемому объекту (явлению), в виде математических соотношений (уравнений, неравенств); эти соотношения образуют систему ограничений задачи;

- количественное выражение выбранного критерия оптимальности в форме целевой функции;

- математическое формулирование задачи как задачи отыскания экстремума целевой функции при условии выполнения ограничений, накладываемых па переменные [1].

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

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

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

- задачи по минимизации дисбаланса на линии сборки (что по существу эквивалентно максимизации выпуска изделий);

- задачи составления кормовой смеси (задача о диете);

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

- задачи о раскрое или о минимизации обрезков (состоят в разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму);

- транспортные задачи (по распределению ресурсов, находящихся у m производителей (поставщиков), n потребителям этих ресурсов) [3].

Обобщая их, можно сделать следующие выводы.

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

2. Линейная функция может стремиться как к максимуму, так и к минимуму.

3. Переменные в задачах всегда неотрицательны.

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

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

 Скачать реферат