для студентов экономических специальностей 5 страница

	2 10	1 40			0 20
	5 20		3 50	5 20
	3 60

4. Проверим полученный опорный план на невырожденность.

Число заполненных ячеек распределительной таблицы равно 7. Для выполнения условия невырожденности плана необходимо, чтобы число заполненных ячеек равнялось , где m – число поставщиков (складов), n – число потребителей (рынков сбыта).

Для данной задачи значение совпадает с число заполненных ячеек. Таким образом, построенный опорный план является невырожденным.

5. Определим потенциалы поставщиков и потребителей .

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

	2 10	1 40			0 20	U1
	5 20		3 50	5 20		U2
	3 60					U3
	V1	V2	V3	V4	V5

Для определения потенциалов составляем уравнения:

Положив , получим

	2 10	1 40			0 20
	5 20		3 50	5 20
	3 60

6. Проверим опорный план на оптимальность.

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

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

Вычислим оценки свободных ячеек:

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

В качестве такой ячейки выберем ячейку (2,5), т.к. она имеет наименьшую оценку .

7. Построим новый опорный план.

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

Построим следующий замкнутый цикл: (2,5) – (2,1) – (1,1) – (1,5) – (2,5). В свободную ячейку с минимальной отрицательной оценкой вписывается знак «+», в вершину, следующую за свободной клеткой в цикле, ставится знак «-» и т.д. по порядку.

«+» 70	2 10	1 40			«-» 0 20
«-» 90	5 20		3 50	5 20	«+» 0
	3 60

Поставка, передаваемая по циклу, определяется как минимум среди поставок в ячейках цикла со знаком «-». Для нашей задачи знак «-» имеют ячейки (2,2), (1,5). Минимальный объем груза для этих ячеек равен .

В вершинах цикла со знаком «+» объем груза увеличивается на 20 единиц, а в вершинах со знаком «-» - уменьшается на тот же объем груза. Например, поставка ячейки (2,5) станет равной 20 единицам груза, ячейки (2,1) и (1,5) станут свободными и т.д. Поскольку ячейки со знаком «-» имеют одинаковый объем поставок, равный 20, то для сохранения невырожденности плана ячейку (1,5) (данная ячейка является клеткой с минимальной стоимостью, и на её основе нельзя построить замкнутого цикла) будем считать условно заполненной с объемом поставки, равным 0.

В результате баланс распределения поставок не нарушается.

Проверим новый опорный план на оптимальность. Снова найдем оценки свободных ячеек. Для этого сначала вычислим потенциалы складов и рынков сбыта заполненных ячеек.

	2 30	1 40	«+» 5	«-» 3	0 0
			«-» 3 50	«+» 5 20	0 20
	3 60

Положив , получим

Вычислим оценки свободных ячеек:

Среди полученных оценок есть отрицательные, значит, найденный опорный план неоптимальный, и следует произвести загрузку свободной ячейки с минимальной оценкой и перейти к новому опорному плану. В качестве такой ячейки выберем ячейку (1,4), т.к. она имеет наименьшую оценку .

Построим следующий замкнутый цикл: (1,4) – (1,5) – (2,5) – (2,4) – (1,4). Определяем поставку, передаваемую по циклу, как . В вершины цикла со знаком «+» объем груза условно увеличивается на 0 единиц груза, а в вершинах со знаком «-» - уменьшается на тот же объем.

Ячейка (1,5) становится свободной, ячейка (1,4) – становится условной заполненной. Поставки в остальных ячейках цикла остаются неизменными.

	2 30	1 40		3 0
			3 50	5 20	0 20
	3 60
					-2

Проверим новый опорный план на оптимальность. Снова найдем оценки свободных ячеек. Для этого сначала вычислим потенциалы складов и рынков сбыта заполненных ячеек.

Положив , получим

Вычислим оценки свободных ячеек:

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

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

Построим замкнутый цикл: (2,2) – (1,2) – (1,4) – (2,4) – (2,2).

	«-» 2 30	1 40		«+» 3
		«+» 2	«-» 3 50	5 20	0 20
	3 60
					-2

Произведем загрузку свободной ячейки с отрицательной оценкой.

Поставка, передаваемая по циклу, определяется как минимум среди поставок в ячейках цикла со знаком «-». Для нашей задачи знак «-» имеют ячейки (1,2), (2,4). Минимальный объем груза для этих ячеек равен .

Поставка ячейки (2,2) станет равной 20 единицам груза, ячейки (1,2) - 20 единицам груза, ячейки (1,4) - 20 единицам груза, ячейка (2,4) станет свободной.

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

	2 30
				«-» 5
					-1

Вычислим потенциалы поставщиков и потребителей для заполненных ячеек.

Положив , получим

Вычислим оценки свободных ячеек:

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

Оптимальный план распределения:

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

Двадцать единиц продукции, находящиеся на 2-ом складе, согласно полученному плану остаются нераспределенными.

10. Задачи производственного менеджмента

1. Задача распределения ресурсов с ограничениями на технико-экономические показатели

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

Имеется целевая функция

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

при граничных условиях:

.

Моделируемая система характеризуется производством нескольких видов продукции (), для выпуска которых требуются имеющиеся в ограниченном количестве различные ресурсы (). Расход i – ого ресурса на единицу продукции j – ого вида равен .

Заданы также общие для системы показатели (), определяющие её деятельность и выполнение которых является обязательным (как правило, это планируемые технико-экономические показатели). Коэффициенты обозначают единичную эффективность j – ого вида продукции по i –ому показателю ().

При заданном потреблении ресурсов показатель эффективности j – ого вида продукции характеризуется величиной .

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

2. Задача размещения производства

Предположим, есть план производства n видов продукции - (Значения получают в результате решения задачи оптимального планирования производства). Для производства используются k видов взаимозаменяемого оборудования (технологических линий или станков).

Оборудование каждого вида с учетом текущего и капитального ремонта не может использоваться более количества времени за планируемый период. Известна производительность k - ого оборудования: - количество продукции j -го вида, производимое i -ым видом оборудования за единицу времени. Предположим, затраты i -го оборудования для производства j -ой продукции в единицу времени составляет . Определить оптимальную загрузку оборудования (количество времени, затраченного оборудованием каждого вида для производства каждого вида продукции).

Экономико-математическая модель задачи:

Целевая функция (затрат)

Ограничения: (Оборудование каждого вида не может быть загружено более, чем на время Ti);

(Суммарный объем производства j – ой продукции на оборудовании всех видов составляет );

.

3. Задача «коммивояжера»

Требуется объехать n пунктов, начиная и заканчивая в одном пункте, таким образом, чтобы суммарные затраты были минимальные. Затраты, связанные с переездом из i – ого пункта в j – ый пункт равны .

Математическая формулировка такой задачи сводится к виду:

Целевая функция

- минимизация суммарного времени.

Ограничения – условия о выезде из каждого i – ого пункта только один раз и въезде в каждый j – ый пункт только один раз (i, j – соответственно номера пунктов выезда и приезда):

Задание для самостоятельной работы

Содержание:

1. Ознакомиться с теоретическим материалом.

2. Выполнить следующие задания.

2.1. Привести пример производственно-экономической задачи, сводящейся к задаче линейного программирования, и её математическую формулировку. Полученную задачу решить в Mathcad.

2.2. Математически сформулировать двойственную задачу, решить её в Mathcad и привести экономическую интерпретацию взаимодвойственных задач.

2.3. Найти наибольшее и наименьшее значения целевой функции Z при заданных ограничениях графическим методом.

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

2.5. Сформулировать задачу, двойственную задаче 2.4., и решить её на основе теорем двойственности.

2.6. Найти целочисленное решение задачи линейного программирования 2.4.

2.7. Решить транспортную задачу с закрытой и открытой моделью.

Варианты задач для самостоятельной работы

1). Решить стандартную задачу линейного программирования:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

2). Решить транспортную задачу.

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

Числовые данные задачи представлены в следующей таблице:

Склады	Торговые точки	Объём вывоза, т
Стоимость перевозки 1 т груза, руб
	a d	e	b c	f
Объём вывоза, т

Варианты задач:

Вариант

a

b

c

d

e

f

Вариант

a

b

c

d

e

f