Математические методы исследования операций в экономике (стр. 3 из 37)

Ограничения на возможные значения хÎ R^mn имеют вид:

1. Ограничение на удовлетворение потребностей во всех пунктах потребления:

2. Ограничения на возможности вывоза запасов из всех пунктов производства:

3. Условия неотрицательности компонентов вектора плана:

х, х_i,j ≥ 0,iÎl : m,jÎl : n. (15)

Существенной характеристикой описываемой модели является соотношение параметров а_iи b_j. Если суммарный объем производства равен суммарному объему потребления, аименно,

то система называется сбалансированной. При выполнении условия сбалансированности разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т. е. условия (13) и (14) приобретают форму равенств.

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

Функция (16) и описанные выше ограничения, записанные в форме

задают транспортную модель. На ее основе может быть сформулирована задача минимизации суммарных затрат на перевозки:

f(x)=cx → min, xÎD, (18)

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

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

Пусть на некотором множествеD определена функцияf(x).Напомним, что точка х*, принадлежащая D (х*Î D), называется точкой глобального максимума, если для любого xÎD выполняется неравенствоf(x) ≤ f(x*). В этом случае значение f(x*) называется глобальным максимумом функции. Точка х̀́ называется точкой локального максимума, если существует некоторая окрестность этой точки, в любой точке которой значение функции меньше, чем в х́̀ (f(x) ≤ f(x́̀)). По аналогии, с точностью до знака неравенства, определяются глобальный и локальныйминимумы. Обобщающим понятием для максимума и минимума является таксой термин, как экстремум (оптимум).

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

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

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

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

ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

1.1.1. Формы задачи линейного программирования.

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

на некотором множествеD Ì Rⁿ, где х ÎD удовлетворяют системе ограничений

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

х₁ ≥0,х₂≥0,..., х_j ≥0,...,х_n≥0. (1.3)

* Напомним, что частные примеры, сводящиеся к задаче линейного программирования, были описаны во введении.

Не умаляя общности, можно считать, что в системе (1.2) первые m ограничений являются неравенствами, а последующие —l-уравнениями. Очевидно, этого всегда можно добиться за счет простого переупорядочения ограничений. Относительно направления знака неравенства будем предполагать, что левая часть меньше или равна правой. Добиться этого можно, умножив на (-1) обе части тех неравенств, которые имеют противоположный знак. Ограничения (1.3), вообще говоря, могут быть рассмотрены как частный случай ограничений в форме неравенств, но в силу особой структуры их обычно выделяют отдельно и называют условиями неотрицательности (или тривиальными ограничениями).

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

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

Часто условия задачи (1.1)-(1.3), содержащей ограничения только типа неравенств, бывает удобно записывать в сокращенной матричной форме

f(x) = сх → max, A_x ≤ b, х ≥ 0, (1.6)

где сих — векторы из пространстваRⁿ,b— вектор из пространстваR^m, а А — матрица размерности mх n.

Задачу линейного программирования, записанную в форме (1.1)-(1.3), называют общей задачей линейного программирования (ОЗЛП).

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

Поскольку любая оптимизационная задача однозначно определяется целевой функцией f и областьюD, на которой отыскивается оптимум (максимум), будем обозначать эту задачу парой (D, f).

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

Планом ЗЛП называется всякий вектор х из пространства Rⁿ.

Допустимым планом называется такой план ЗЛП, который удовлетворяет ограничениям (1.2)-(1.3), т. е. содержится в области D. Сама область D называется при этом областью допустимых планов. Оптимальным планомх* называется такой допустимый план, при котором целевая функция достигает оптимального (в нашем случае — максимального) значения, т. е. план, удовлетворяющий условию

max f(x) = f(x*).

Величина f* =f(х*) называется оптимальным значением целевой функции.

Решением задачи называется пара (х*, f*), состоящая из oптимального плана и оптимального значения целевой функции, а процесс решения заключается в отыскании множества всех решений ЗЛП.

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