Файл: Курс лекций.doc

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