Методические указания по изучению дисциплины и выполнению контрольной работы (стр. 10 из 14)

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

В данной задаче требуется максимизировать целевую функцию P, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию P на противоположную функцию Z=-P, которую нужно будет минимизировать.

При решении в транспортной таблице вместо тарифов на перевозки запишутся производительности p_ij, взятые с противоположным знаком. Далее задача решается как обычно.

2. Формирование оптимального штата фирмы.

Фирма набирает штат сотрудников. Она располагает n группами различных должностей по b_j вакантных единиц в каждой группе,

Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по a_i кандидатов в каждой группе,

Для каждого кандидата из i-й группы требуются определенные затраты c_ij на обучение для занятия j-й должности,

(В частности, некоторые c_ij=0, т.е. кандидат полностью соответствует должности, или c_ij=

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

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

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

Математическая модель задачи имеет следующий вид:

Методы решения этой задачи такие же, как и транспортной задачи.

ПРИМЕР 2. Имеется m видов сельскохозяйственных культур и n хозяйств, где их можно выращивать. Из-за различных условий доход, получаемый с 1 га посева одной и той же культуры, в различных хозяйствах неодинаков. Обозначим через c_ij доход для i-й культуры и j-го хозяйства. Общие площади посева культур a_i (i=1,m) и площади пашни в хозяйствах b_j (j=1,n) известны. Требуется составить такой план размещения сельскохозяйственных культур по хозяйствам, чтобы общий доход был максимальным.

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

Найти план X=(x_ij) такой, что

При условиях:

а) план посева по каждой культуре должен быть выполнен

б) пашня в хозяйствах должна быть использована полностью

в)

4. Нелинейное программирование

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

4.1 Общая задача нелинейного программирования

В общем виде ЗНП формулируется следующим образом:

, (4.1)

, (4.2)

, (4.3)

где

- управляющие переменные или решения ЗНП;

- фиксированные параметры;

- заданные функции от n переменных, причем целевая функция

или (и) хотя бы одна из функций

являются нелинейными.

Решить задачу нелинейного программирования - это значит найти такие значения управляющих переменных

, которые удовлетворяют системе ограничений (4.2),(4.3) и доставляют максимум или минимум целевой функции

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

Процесс составления математической модели ЗНП принципиально не отличается от составления модели ЗЛП. Рассмотрим несколько примеров.

Задача 4.1. На m предприятиях выпускается некоторый продукт. Себестоимость единицы этого продукта на каждом из указанных предприятий есть

, где

- доля себестоимости, не зависящая от объема выпуска продукции,

- план выпуска продукта на i-м предприятии.

Предприятия должны обеспечить n потребителей с потребностями

, стоимость перевозки из i-го предприятия к j-му потребителю равна

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

Математическую модель задачи. Пусть

- план перевозок от i-го предприятия к j-му потребителю.

Для удобства запишем данные и искомые величины задач в виде таблицы:

Табл.4.1

Потребители Предприятия	1	2	...	n	План выпуска изделий
1	x₁₁	x₁₂	...	x_1n	x₁
2	x₂₁	x₂₂	...	x_2n	x₂
...
m	x_m1	x_m2	x_mn	x_m
Потребности заказчиков	b₁	b₂	...	b_n

Система ограничений задачи:

(4.4)

Целевая функция f запишется так:

Вместо

подставим значения, данные в условии задачи:

(4.5)

Надо найти минимальное значение функции (6.5) на множестве допустимых решений (4.4).

Задача 4.2. На производство некоторого продукта расходуется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов, если цена ресурса первого вида 30 рублей, второго - 40 рублей, а всего выделено на производство 120 рублей. Известно, что из количества x₁ первого ресурса и x₂ второго ресурса можно получить

единиц продукта.

Вообще, функция

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

где

- постоянные величины, причем