Линейное программирование

Размещено на http://www.allbest.ru/

Задание 1. Применение методов линейного программирования

прибыль планирование перевозка

Постановка задачи.

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

Продукция Сырье	A	B	C	Запасы сырья, ед.
I	-	1	1	7
II	2	1	-	14
III	1	1	-	10
Прибыль, ден.ед.	4	5	1

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

Требуется:

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

2) Выбрать метод решения и привести задачу к канонической форме.

3) Решить задачу (симплекс-методом).

4) Дать геометрическую интерпретацию решения.

5) Проанализировать результаты решения.

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

7) Решить двойственную задачу (двойственным симплекс-методом).

8) Дать экономическую интерпретацию двойственных оценок.

Решение:

1) Чтобы сформулировать эту задачу математически, обозначим через , и количество единиц продукции соответственно видов A, B и C, которое необходимо выпускать для получения максимальной прибыли. Согласно условиям задачи прибыль от выпуска продукции вида А составит 4 ден.ед., от вида В - 5 ден.ед., от вида С - 1 ден.ед. Следовательно, целевая функция прибыли z выразится формулой:

.

Поскольку переменные , и определяют количество единиц продукции, они не могут быть отрицательными, то есть

, .

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

На изготовление всей продукции будет использовано ед. сырья II вида, запасы которого составляют 14 ед., тогда должно выполняться неравенство: .

Для сырья III вида должно выполняться неравенство: .

Следовательно, система ограничений будет иметь вид:

Итак, задача состоит в том, чтобы найти неотрицательные значения , и , удовлетворяющие системе ограничений и максимизирующие целевую функцию z.

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

,

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

.

3) Решим задачу симплекс-методом. Найдем начальный опорный план задачи. Все ограничения системы имеют предпочтительный вид. Базис образуют переменные , . Для получения опорного решения приравняем свободные переменные к нулю, а базисные - свободным членам, то есть , , . Тогда начальный опорный план задачи: , а значение целевой функции в этой точке .

Выразим целевую функцию через свободные переменные . Составим исходную симплекс-таблицу.

Б	З
	7	0	1	1	0	0	-
	14	2	1	0	1	0	7
	10	1	1	0	0	1	10
z	7	-4	-4	0	0	0

Так как в z-строке есть отрицательные, то опорный план не является оптимальным. Ведущий столбец первый, так как ему соответствует отрицательный элемент -4. Ведущую строку выбираем по минимальному симплексному отношению: . Таким образом, вторая строка ведущая, - ведущий элемент. Значит переменная будет включена в базис, а переменная из базиса выводится.

Каждый элемент ведущей строки разделим на ведущий элемент. Запишем полученную строку в новую симплекс таблицу. Остальные элементы ведущего столбца делаем нулевыми. Первую строку переписываем, так как элемент её первого столбца уже равен 0. Чтобы в третьей строке вместо 1 получить 0, необходимо каждый элемент строки, полученной из ведущей, умножить на (-1) и прибавить почленно к 1-й строке. Чтобы в z-строке вместо -4 получить 0 нужно строку, полученную из ведущей, умножить на 4 и прибавить к z-строке. Таблицы пересчитываем до тех пор, пока в z-строке все элементы (не считая значения) станут неотрицательными.

Б	З
	7	0	1	1	0	0	7
	7	1	0,5	0	0,5	0	14
	3	0	0,5	0	-0,5	1	6
z	35	0	-2	0	2	0

Б	З
	1	0	0	1	1	-2	1
	4	1	0	0	1	-4	4
	6	0	1	0	-1	2	-
z	47	0	0	0	0	4

Так как в z-строке все элементы больше или равны нулю, то найден оптимальный план: , .

Оптимальный план не единственный, так как в z-строке есть нули, соответствующие не только базисным переменным. Найдем второй оптимальный план

Б	З
	1	0	0	1	1	-2
	3	1	0	-1	0	-2
	7	0	1	1	0	0
z	47	0	0	0	0	4

, .

Общее решение запишем как выпуклую линейную комбинацию опорных решений и : , где и , . Следовательно, .

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

,

Полученную графическим способом.

(рисунок 1)

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

.

, где и , .

5) Итак, чтобы получить максимальную прибыль, равную 47 ден.ед. необходимо: 1. По выпускать 4 ед. продукции вида А, 6 ед. продукции вида В и 1 ед. продукции вида С. Все сырье будет использовано.

2. По - выпускать 3 ед. продукции вида А, 7 ед. продукции вида В и не выпускать продукцию вида С. При этом 1 ед. сырья вида будет не использована, так как .

6)Составим к данной задаче двойственную. Каждому ограничению исходной задачи поставим в соответствие двойственную переменную , .

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

Зная оптимальное решение прямой задачи, выпишем ответ двойственной задачи. Базисным переменным прямой задачи , поставим в соответствие свободные переменные двойственной задачи .

Б	З
	7	0	1	1	0	0
	14	2	1	0	1	0
	10	1	1	0	0	1
z	7	-4	-4	0	0	0

Перепишем их под последнюю симплекс-таблицу:

Б	З
	1	0	0	1	1	-2
	4	1	0	0	1	-4
	6	0	1	0	-1	2
z	47	0	0	0	0	4

Решение двойственной задачи находим по последней симплекс-таблице в строке оценок.

, (так как в целевой функции коэффициент при равен 1)

, (так как в целевой функции коэффициент при равен 0)

, (так как в целевой функции коэффициент при равен 0)

.

7) Решим двойственную задачу двойственным симплекс-методом. Приведем задачу к каноническому виду:

Задача имеет базисное решение (псевдо-план) , .

Б	З
	-4	0	-2	-1	1	0	0
	-5	-1	-1	-1	0	1	0
	-1	-1	0	0	0	0	1
	0	7	14	10	0	0	0

Б	З
	-4	0	-2	-1	1	0	0
	5	1	1	1	0	-1	0
	4	0	1	1	0	-1	1
	-35	0	7	3	0	7	0



Б	З
	4	0	2	1	-1	0	0
	1	1	1	0	1	-1	0
	0	0	-1	0	1	-1	1
	-47	0	1	0	3	7	0

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

Решение единственно, так как нулевые элементы z-строки соответствуют только базисным переменным , , .

8) Дадим экономическую интерпретацию двойственных оценок.

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

Увеличение сырья I-го вида на 1 ед. приведет к тому, что появится возможность найти оптимальный план производства продукции, при котором общая стоимость возрастет на ден.ед. и станет равной 47+1=48 ден.ед. Аналогично, увеличение сырья III-го вида на 1 ед. приведет к увеличению общей стоимости на 4 ден.ед.: 47+4=51 ден.ед.



Задание 2. Планирование перевозок

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

Требуется:

1) Свести исходные данные в таблицу:

Магазин База			…		Запасы товаров на базах, тыс.ед.
			…
			…
…	…	…	…	…	…
			…
Потребности магазинов, тыс.ед.			…

2) Составить математическую модель задачи;

3) Привести ее к стандартной транспортной задаче (с балансом);

4) Построить начальный опорный план задачи (методом минимального элемента);

5) Решить задачу (методом потенциалов);

6) Проанализировать результаты решения.

, , .

Необходимо полностью освободить 3-ю базу.

Решение:

1) Сведем исходные данные в таблицу:

Магазин База						Запасы товаров на базах, тыс.ед.
	4	8	3	6	7	30
	8	4	6	5	9	25
	3	5	8	5	4	20
	5	8	10	6	8	15
Потребности магазинов, тыс.ед.	10	20	18	12	25	90 85

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

Или

Требуется спланировать перевозки так, чтобы товар из пунктов отправления был вывезен. Но так как суммарный объем товара, вывезенного с каждой базы, не может превышать запасов товара на базах, то переменные должны удовлетворять следующим ограничениям по запасам (так как запасы товаров (90 тыс.ед.) больше, чем потребности магазинов в товаре (85 тыс.ед.), то не все базы будут освобождены), т.е. должны выполняться неравенства:

(для 1-й базы)

(для 2-й базы)

(для 3-й базы)

(для 4-й базы)

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

(для 1-го магазина)

(для 2-го магазина)

(для 3-го магазина)

(для 4-го магазина)

(для 5-го магазина)

Объем перевозок товара не может быть отрицательным, поэтому (, ).

3) Транспортная задача разрешима только в том случае, когда выполняется условие баланса: . В нашем случае оно нарушено, так как , . Следовательно, задача является открытой, несбалансированной. Так как , то введем фиктивный магазин , потребности в товаре которого составляют тыс.ед. Согласно условию необходимо полностью освободить 3-ю базу, следовательно, стоимость транспортных расходов на доставку 1 тыс.ед. товара с 3-й базы в фиктивный магазин необходимо сделать невыгодной, например, . Пусть . А стоимость транспортных расходов на доставку 1 тыс.ед. товара с остальных баз в фиктивный магазин будем полагать равной нулю, , . Получим следующую закрытую модель транспортной задачи:



,

(, ).

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

	10	20	18	12	25	5
30	+	4 -2		8 3	18	3	7	6	5-	7		0 1	0
25		8 3	20	4		6 4	5	5		9 3		0 2	-1
20	10-	3		5 3		8 8		5 2	10+	4		11 15	-3
15		5 -2		8 2		10 6		6 -1	10	8	5	0	1
	6	5	3	6	7	-1



Проверим условие для базисных клеток (их должно быть п+m-1): п+m-1=4+6-1=9. Заполнено также 9 клеток. Следовательно, начальный опорный план построен верно. При этом значение целевой функции будет равно:

(ден.ед.)

5) Вычислим потенциалы и . Для базисных клеток : .

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

	10	20	18	12	25	5
30	5+	4		8 3	18	3	7-	6		7 2		0 3	0
25		8 5	20	4		6 4	5	5		9 5		0 4	-1
20	5-	3		5 1		8 6		5 0	15+	4		11 15	-1
15		5 -2		8 0		10 4	+	6 -3	10-	8	5	0	3
	4	5	3	6	5	-3

(ден.ед.)

	10	20	18	12	25	5
30	10	4		8 3	18	3	2-	6	+	7 -1		0 0	0
25		8 5	20	4		6 4	5	5		9 2		0 1	-1
20		3 3		5 4		8 9		5 3	20	4		11 15	-4
15		5 1		8 3		10 7	5+	6	5-	8	5	0	0
	4	5	3	6	8	0

(ден.ед.)

	10	20	18	12	25	5
30	10	4		8 4	18	3		6 1	2	7		0 1	0
25		8 4	20	4		6 3	5	5		9 2		0 1	0
20		3 2		5 4		8 8		5 3	20	4		11 15	-3
15		5 0		8 3		10 6	7	6	3	8	5	0	1
	4	4	3	5	7	-1

(ден.ед.)

Полученный опорный план оптимален, так как среди оценок нет отрицательных. Выпишем его:

, (ден.ед.)

6) Итак, чтобы привезти товар с минимальными затратами 359 (ден.ед.), необходимо с первой базы в 1-й, 3-й и 5-й магазины доставить 10, 18 и 2 тыс.ед. товара соответственно, со 2-й базы во 2-й и 4-й магазины доставить 20 и 5 тыс.ед. товара соответственно, с 3-й базы в 5-й магазин доставить 20 тыс.ед товара, с 4-й базы - в 4-й и 5-й магазины доставить 7, 3 тыс.ед. товара соответственно. Наличие 5 тыс.ед. товара в фиктивном магазине свидетельствует о том, что при условии полного удовлетворения потребностей всех магазинов, четвертая база не будут освобождена полностью, там останется 5 тыс.ед. товара.

Задание 3. Предприятие планирует открыть филиалы в Михайловке, Урюпинске и Котельниково, для чего выделяются средства в размере 5 млн.руб. По расчетам экономистов, каждый филиал при инвестировании в него х тыс.руб. приносит прибыль тыс.руб. Эти данные приведены в таблице:

Вложенные средства (х млн.руб.)	филиал
	Михайловка	Урюпинск	Котельниково
1	0,50	0,40	0,60
2	1,00	0,65	0,80
3	1,50	0,80	1,00
4	2,00	0,90	1,20
5	2,50	1,50	1,30

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

Решение:

1. Построение экономико-математической модели задачи.

1.1. Число шагов равно числу филиалов m=3.

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

1.3. - количество средств, инвестируемых в i-ый филиал.

1.4. Выигрыш на i-ом шаге определяется формулой . Это прибыль, которую приносит i-ый филиал при инвестировании в него средств .

Общая прибыль всего проекта, естественно, составит:

1.5. Если в наличии имеются средства S, и в i-ый филиал вложено х тыс.руб., то для дальнейшего инвестирования остается (S -х) тыс.руб. Эту фразу можно сформулировать иначе на языке динамического программирования: если на i-ом шаге система находится в состоянии S, и выбрано управление х, то на (i+1)-ом шаге система окажется в состоянии (S -х). Таким образом, функция перехода в новое состояние имеет вид:

1.6. Обозначим через выигрыш с i-го шага до конца процесса при условии, что к началу i-го шага система находится в состоянии S. Например, - прибыль, получаемая от вложения 3 млн.руб. во 2 и 3 филиалы.

1.7. Составим функциональное уравнение - уравнение, выражающее через . Функциональное уравнение выражает оптимальный выигрыш для данного состояния S с i-го шага до конца процесса через известный оптимальный выигрыш с (i+1)-го шага до конца процесса. Сначала составим функциональное уравнение для i=m, т.е. последнего шага. Для этого заметим, что на последнем шаге, т.е. перед инвестированием в последний филиал, оптимальное управление соответствует количеству оставшихся в наличии средств, т.е. сколько денег осталось, столько и вкладываем в 3-ий филиал. Выигрыш при этом равен доходу последнего филиала от вложения в него оставшихся средств:

,

.

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

Пусть перед инвестированием средств в i-ый филиал осталось S млн.руб. Тогда х млн.руб. можно вложить в i-ый филиал, и он принесет прибыль . Оставшиеся (S-х) млн.руб. вкладываются в остальные филиалы с (i+1)-го до m-го, которые принесут прибыль . Оптимальным будет такое управление, при котором

.

Отсюда получаем основное функциональное уравнение:

.

Например, при i=1 уравнение примет вид:

.

Это , что в первый филиал надо вложить столько средств, чтобы сумма прибыли, приносимой им и оставшимися 2-м и 3-м филиалами, была максимальна.

2. Условная оптимизация.

Результаты вычислений будем заносить в сводную таблицу: в первом столбце записываем возможные состояния системы (S=1, 2, 2, 4, 5), в верхней строке (шапке) - номера филиалов, соответствующие номеру шага (i=1, 2,3). На каждом шаге определяем условные оптимальные управления и соответствующие им выигрыши .

2.1. Условная оптимизация для i=3.

В соответствие с принципом оптимальности Беллмана, лежащего в основе методов динамического программирования, условную оптимизацию начинаем с последнего шага, т.е. с 3-го филиала.

Функциональное уравнение имеет вид:

,

.

Поэтому столбцы для i=3 заполняем автоматически на основе исходной таблицы. В последнем филиале - сколько средств осталось, столько и вкладываем. Получаем таблицу условной оптимизации №1:

S	i=3	i=2	i=1
1	1	0,60
2	2	0,80
3	3	1,00
4	4	1,20
5	5	1,30

2.2. Условная оптимизация для i=2.

Функциональное уравнение имеет вид:

.

Это означает, что во второй филиал надо вложить столько средств, чтобы сумма прибыли, полученной от него от 3-го филиала была максимальна.

Необходимо рассмотреть пять случаев.

Случай S=1:

х	1-х
0	1	0	0,60	0+0,60=0,60
1	0	0,40	0	0,40+0=0,40

, следовательно, , .

Случай S=2:

х	2-х
0	2	0	0,80	0+0,80=0,80
1	1	0,40	0,60	0,40+0,60=1,00
2	0	0,65	0	0,65+0=0,65

, следовательно, , .

Случай S=3:

х	3-х
0	3	0	1,00	0+1,00=1,00
1	2	0,40	0,80	0,40+0,80=1,20
2	1	0,65	0,60	0,65+0,60=1,25
3	0	0,80	0	0,80+0=0,80

, следовательно, , .

Случай S=4:

х	4-х
0	4	0	1,20	0+1,20=1,20
1	3	0,40	1,00	0,40+1,00=1,40
2	2	0,65	0,80	0,65+0,80=1,45
3	1	0,80	0,60	0,80+0,60=1,40
4	0	0,90	0	0,90+0=0,90

, следовательно, , .

Случай S=5:

х	5-х
0	5	0	1,30	0+1,30=1,30
1	4	0,40	1,20	0,40+1,20=1,60
2	3	0,65	1,00	0,65+1,00=1,65
3	2	0,80	0,80	0,80+0,80=1,60
4	1	0,90	0,60	0,90+0,60=1,50
5	0	1,50	0	1,50+0=1,50

, следовательно, , .

Полученные результаты заносим в таблицу и получаем сводную таблицу условной оптимизации №2:

S	i=3	i=2	i=1
1	1	0,60	0	0,60
2	2	0,80	1	1,00
3	3	1,00	2	1,25
4	4	1,20	2	1,45
5	5	1,30	2	1,65

2.3. Условная оптимизация для i=1.

Функциональное уравнение имеет вид:

.

Т.е. в первый филиал надо вложить столько средств, чтобы сумма прибыли, полученной от него и от 2-го и 3-го филиалов, была максимальна. Поскольку этот филиал первый, то мы располагаем всей суммой S=D=5 млн.руб. Поэтому условную оптимизацию проводим только для S=5.

х	5-х
0	5	0	1,65	0+1,65=1,65
1	4	0,50	1,45	0,50+1,45=1,95
2	3	1,00	1,25	1,00+1,25=2,25
3	2	1,50	1,00	1,50+1,00=2,50
4	1	2,00	0,60	2,00+0,60=2,60
5	0	2,50	0	2,50+0=2,50

, следовательно, , .

Полученные результаты заносим в таблицу и получим сводную таблицу условной оптимизации №3:

S	i=3	i=2	i=1
1	1	0,60	0	0,60
2	2	0,80	1	1,00
3	3	1,00	2	1,25
4	4	1,20	2	1,45
5	5	1,30	2	1,65	4	2,60

3. Безусловная оптимизация.

Проводим безусловную оптимизацию в «прямом» порядке - от 1-го к 3-му филиалу.

1) . В первый филиал надо вложить млн.руб., в результате чего для 2-го и 3-го филиалов остаётся 1 млн.руб.

2) . Во второй филиал надо вложить млн.руб., в результате чего для 3-го филиала остаётся 1 млн.руб.

3) . Следовательно, .

Ответ: для получения максимальной прибыли в размере 2,6 млн.руб. необходимо в первый филиал вложить 4 млн.руб., а в 3-й филиал вложить 1 млн.руб.

Размещено на Allbest.ru

...