Основные типы линейных экономико-математических моделей

 

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

1 модель общей задачи линейного программирования;

2 модель транспортной задачи линейного программирования;

3 модель распределительной задачи линейного программирования;

4 модель ассортиментной задачи линейного программирования.

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

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

1.1 Модель оптимального планирования товарооборота. Торговое предприятие реализует товары нескольких групп: А, В, С. Для реализации единицы товара группы А затраты рабочего времени составляют a₁₁ чел.-ч., товара группы В – a₁₂ чел.-ч., товара группы С – a₁₃ чел.-ч. Площадь торгового зала, занимаемая единицей товара А, составляет а₂₁ м², товара В – а₂₂ м², товара С – а₂₃ м². Расходы (издержки обращения) при продаже единицы товара группы А составляют а₃₁ ден. ед., группы В – а₃₂ ден. ед., группы С – а₃₃ ден. ед. Известны величины ресурсов: рабочее время – b₁ чел.-час., площадь торгового зала b₂ м², издержки обращения b₃ ден.ед. Доход при реализации единицы товара группы А равен c₁ ден. ед., товара группы В – c₂ ден. ед., товара группы С – c­₃ ден. ед.

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

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

 

f = (c₁ x₁ + c₂ х₂ + c₃ х₃) → max. (2.5)

 

Очевидно, что объем продажи товаров не может быть отрицатель­ной величиной. Поэтому x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0. Учитывая нормы за­трат рабочего времени и то, что общие затраты в целом не должны превышать имеющихся ресурсов, запишем следующее ограничение:

(2.6)

 

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

 

(2.7)

 

Поскольку известны ограничения по издержкам обращения, запи­шем последнее ограничение

(2.8)

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

Экономико-математическая постановка задачи. Допустим, имеется набор продуктов: мясо, рыба, молоко, сахар, яйца, картофель, овощи, фрукты, хлеб, мука по цене соответственно: с₁, …, с_n, причем запасы этих продуктов ограничены: а₁, …, а_n.

Содержание питательных веществ – белков, жиров, углеводов, витаминов и минеральных солей – в 1 кг каждого продукта известно и составляет соответственно: q₁₁, q₂₁, …, q_i1, …, q_mn. Кроме того, известны нормы суточной потребности человека в каждом питательном веществе: b₁, b₂, …, b_m.

Перечисленные показатели можно записать в виде системы линейных ограничений:

(2.9)

 

Еще одно ограничение связано с тем, что количество каждого продукта в рационе, с одной стороны, не может быть величиной отрицательной, а с другой — его покупка ограничена запасами:

 

(2.10)

 

В задаче необходимо определить такое количество закупаемых продуктов, которое бы обеспечило потребность человека в питательных веще­ствах при минимальной стоимости набора и описывалось бы линейной формой связи целевой функции:

 

. (2.11)

1.3 Модели рационального распределения материальных ресурсов. В общем виде данная задача может быть сформулирована следующим об­разом:

а) имеется т видов исходных материальных ресурсов, объемы которых ограничены определенной величиной а_i; i = l, 2, ..., m;

б) из этих ресурсов необходимо изготовить п видов продук­ции, при этом минимальный объем выпуска продукции каждо­го вида b_j задан в производственном плане; j = 1, 2,…, n;

в) заданы нормы расхода ресурса i-го вида на выпуск едини­цы j-ой продукции a_ij, которые принимаются постоянными, не зависящими от объема выпуска продукции;

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

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

Экономико-математическая постановка задачи. Обозначим через х_j количество продукции j-го вида, ко­торое следует изготовить в целях удовлетворения выбранного критерия оптимальности. Требуется определить множество не­отрицательных переменных х_ij > 0, где j = 1,2,…,n, удовлетво­ряющих ограничениям по ресурсам

(2.12)

 

и ограничениям по плану производства

 

. (2.13)

 

При этом целевая функция имеет вид

 

- для прибыли , (2.14)

- для себестоимости . (2.15)

 

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

В общем виде задача о смесях может быть сформулирована следующим образом. Состав готовой продукции определяется содержанием в нем т видов элементов, содержание которых лимитируется величиной l_i (i = 1, 2, ..., m). Для k элементов, ухудшающих качество продукции, задана верхняя граница со­держания того или иного элемента ( ), а для (m - k) элемен­тов, улучшающих качество продукции, задана нижняя грани­ца содержания элемента в готовой продукции ( ). Для производства готовой продукции может быть использовано n видов компонентов, объемы которых ограничены величиной b_j (j = 1,2,..., n). Известно содержание i-го элемента в j-ом компо­ненте, которое обозначим как а_ij. Известна стоимость отдель­ных компонентов, включая расходы на их переработку, кото­рую обозначим как с_j. Наконец, задано общее количество М готовой продукции, которое следует изготовить по плану. Тре­буется составить такую смесь из имеющихся компонентов, что­бы затраты на это составление были минимальными.

Экономико-математическая постановка задачи. Обозначим количество используемого для составления сме­си j-го компонента через x_j, вектор, координатами которого яв­ляются величины x_j, обозначим через . Целевая функция за­дачи имеет вид

 

, (2.16)

 

а ограничения формируются следующим образом:

 

(2.17)

(2.18)

(2.19)

(2.20)

 

Ограничения (2.17) относятся к элементам, ухудшающим качество; (2.18) - к элементам, улучшающим качество; (2.19) - по плану производства; (2.20) - по ограничению ресурсов.

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

 

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

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

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

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

Математически транспортная задача по критерию стоимости формируется следующим образом.

2.1 Статическая модель оптимизации прикрепления потребителей к поставщикам. В т пунктах отправления A₁, A₂, ..., А_m, которые в дальней­шем будем называть поставщиками, сосредоточено определен­ное количество единиц некоторого однородного продукта, кото­рое обозначим a_i (i = 1, 2,..., т).

Данный продукт потребляется в n пунктах B₁, B₂, ..., B_n, ко­торые будем называть потребителями; объем потребления обо­значим b_j (j = 1, 2, …, n).

Известны расходы на перевозку единицы продукта из пункта А_i в пункт В_j, которые равны c_ij и приведены в матрице транс­портных расходов С = (c_ij).

Требуется составить такой план прикрепления потребите­лей к поставщикам, другими словами, план перевозок, при котором весь продукт вывозится из пунктов A_i в пункты B_j в со­ответствии с потребностью и общая величина транспортных из­держек минимальна.

Экономико-математическая постановка задачи. Обозначим количество продукта, перевозимого из пункта А_i в пункт В_j через x_ij. Совокупность всех переменных x_ij для краткости обозначим символом , тогда целевая функция задачи приобретет вид

 

, (2.21)

 

а ограничения выглядят следующим образом:

 

(2.22)

; (2.23)

. (2.24)

 

Условия (2.22) означают полное удовлетворение спроса во всех пунктах потребления; условия (2.23) определяют полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости зада­чи (2.21-2.24) является условие баланса

. (2.25)

 

Транспортная задача, в которой имеет место равенство (2.25), называется закрытой и может быть решена как задача линейного программирования.

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

Имеется т предприятий (например, филиалов фирмы), ко­торые могут производить n видов продукции. Известны:

а) а_i - фонд рабочего времени (например, в сменах) каждого i-го предприятия; i = 1, 2,..., т;

б) b_j - величина потребности в продукции j-го вида; j = 1, 2, ..., п;

в) a_ij - мощность, или количество продукции j-го вида, выра­батываемой (в смену) на i-ом предприятии;

г) c_ij - себестоимость производства единицы j-ой продукции на i-ом предприятии.

Требуется составить такой план распределения заказов на продукцию по всем предприятиям, при котором суммарные за­траты по изготовлению продукции в заданной номенклатуре будут минимальными при полной загрузке производственных мощностей предприятий.

Экономико-математическая постановка задачи. Пусть x_ij - планируемый объем выпуска j-ой продукции на i-ом предприятии; совокупность таких величин обозначим . Тогда целевая функция рассматриваемой задачи имеет вид

 

(2.26)

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

; (2.27)

(2.28)

. (2.29)

 

Если снять условие полной загрузки производственных мощностей предприятий, то ограничения (2.27) примут вид не­равенств

 

; (2.30)

 

если условие точного выполнения плана в заданной номенкла­туре заменить требованием «не меньше», то условия (2.28) пре­вратятся в неравенства

 

. (2.31)

 

Очевидно, задачу (2.26) - (2.29) можно решить как задачу линейного программирования. Однако если привести определенными приемами коэффициент а_ij к единице, то данная модель не будет отличаться от модели транс­портной задачи.

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

Приведем следующий пример. В универмаге имеется n работников: A₁, А₂, ..., А_i, …, A_n, каждый из которых может выполнять одну В_j из имеющихся n видов работ: B₁, B₂, ..., B_j, …, B_n.

Для каждого работника А_i на любом рабочем месте В_j известна производительность труда а_ij. Полагаем, что если работник назна­чен на работу В_j, то переменная назначения х_ij = 1, или x_ij = 0, если он на эту работу не назначен, что можно записать так

(2.32)

 

Условия задачи удобно записать в виде двойной матрицы и .

Если работник А₁ назначен на работу B₁, то x₁₁ = 1, а остальные элементы назначения первой строки и пер­вого столбца равны нулю. Из этого следует, что сумма пере­менных любой строки или столбца равна 1. Перечисленные огра­ничения задачи можно записать таким образом:

(2.33)

 

В качестве критерия оптимальности выбираем суммарную про­изводительность работников. Тогда целевую функцию можно запи­сать таким образом:

 

. (2.34)

 

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

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

В общем виде эту задачу можно сформулировать следую­щим образом. Имеется n городов, занумерованных числами от 1 до n. Ком­мивояжер, выезжая из города 1, должен побывать в каждом го­роде ровно один раз и вернуться в исходный пункт. Известны расстояния c_ij ( ) между городами. Требуется найти самый короткий маршрут.

Введем переменные:

 

(2.35)

 

Требования однократного въезда и выезда из каждого горо­да запишутся в виде

 

(2.36)

 

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

 

. (2.37)

 

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

Таким образом, задача коммивояжера состоит в минимиза­ции:

 

(2.38)

 

при условиях (2.36) и (2.37), где переменные х_ij, U_i принимают только неотрицательные целые значения.

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

2.5 Задача о размещении складов является одной из оптимиза­ционных задач исследования операций и решается обычно ме­тодами нелинейного программирования. Задача заключается в минимизации общей суммы транспортных и складских расхо­дов при следующих ограничениях:

а) с каждого предприятия должна быть отгружена вся про­дукция;

б) не может быть превышена емкость ни единого склада;

в) должны быть удовлетворены заявки всех потребителей.

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

3 Модель распределительной задачи линейного программирования часто называют обобщенной транспортной задачей. Наиболее типичными для ее интерпретации являются задачи использования взаимозаменяемых ресурсов.

Приведем следующий пример. В цеху изготовляются n видов изделий, причем каждое изделие может производиться на любом из имеющихся m групп обо­рудования. Время изго­товления и затраты по обработке отдельных изделий j-ого вида на станках i-ой группы равны λ_ij ч и c­_ij ден. ед. Имеется заказ на изготовление b_j изделий j-го вида. Наличное время работы станков ограничено, оно составляет а_i станко-часов для i-ой группы оборудования.

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

Экономико-математическая модель задачи. Обозна­чив через x_ij количество изделий j-го вида, обрабатываемых на i-ой группе оборудования, приходим к следующей математической модели распределительной за­дачи:

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

 

(2.39)

 

2) время работы отдельных групп оборудования ограничено:

 

(2.40)

 

3) количество обрабатываемых изделий на различных группах обо­рудования должно выражаться неотрицательными числами:

 

(2.41)

 

4) общая сумма затрат на обработку изделий должна быть мини­мальной:

 

. (2.42)

 

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

 

4 Модель ассортиментной задачи линейного программирования сформулирована Л. В. Конторовичем. Им же разработан ме­тод решения задач данного класса. Ее можно решать на основе системы ограничений общей или распределительной задачи линейного программирования.

Особенность целевой функции состоит в том, что ставится задача максимизации количества комплектов изделий, то есть

 

, (2.43)

 

где с - количество комплектов;

k_j - количество j-х изделий, входящих в комплект ( );

х_j - количество производимых изделий j-го вида.

 

Модель ассортиментной задачи в системе ограничений об­щей задачи линейного программирования:

1) учитываются лимитирующие условия в задаче:

 

; (2.44)

2) соблюдается неотрицательность переменных величин:

 

; (2.45)

 

3) максимизируется производство комплектной продукции:

 

, (2.46)

 

где a_ij - расход лимитирующего ресурса i-го вида на j-ое изде­лие;

а_i - располагаемый фонд ресурса i-ro вида.

 

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

1) учитывается время работы i-ой группы оборудования:

 

(2.47)

 

2) количество обрабатываемых изделий на различных группах оборудования должно выражаться неотрицательным числом:

 

(2.48)

 

3) максимизируется производство комплектной продукции:

 

, (2.49)

 

где λ_ij - время обработки j-го изделия на i-й группе оборудования;

А_i - располагаемый фонд времени работы i-й группы обо­рудования;

с - количество комплектов;

k_j - количество j-х изделий, входящих в комплект;

х_ij - количество изделий j-го вида, обрабатываемых на i-й группе оборудования.