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

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

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

Федеральное агентство железнодорожного транспорта

Уральский государственный университет путей сообщения

Кафедра высшей математики

КУРСОВОЙ ПРОЕКТ

по предмету

Математическое моделирование

тема:

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

Выполнил: студент группы ЭкТ

Сычёв А.В.

Проверил: преподаватель

Филипова Е.Г.

Екатеринбург, 2010 г.



Графическое решение задач линейного программирования

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

продукт	расход на 1 кг.	запас, кг.
	клубничное	малиновое
ягоды	2	5	50
сахар	4	3	44
вода	4	1	36

Розничная цена 1 килограмма клубничного варенья равна 2 евро, а малинового 1 евро.

Найти: Какое количество каждого вида повидла должна производить фирма, чтобы доход от реализации был максимальным.

Решение:

Пусть x₁, кг. - необходимое количество клубничного варенья; x₂, кг. - необходимое количество малинового варенья. ( ₁, ₂ ?0)

Тогда получим систему ограничений:

> max

Задача составлена. Решим ее графически.

1. Построим прямые

:



	10	0
	6	10
	5	8
	8	4
	7	8
	8	4

Общее решение: A, B, C

Общее допустимое решение: A, B, C, D, 0, A

2. ={16;14} - нормальный вектор целевой функции. Строи линию уровня и передвигаем ее в сторону нормального вектора целевой функции до тех пор, пока она не коснется фигуру ровно один раз.

3. Таким образом оптимальное решение достигается в вершине С, С =

4. C: _?- 4 ?

5. Таким образом, для того, чтобы доход был максимальным необходимо изготавливать 8 килограмм клубничного варенья и 4 килограмма малинового. При этом доход от реализации продукции составляет:

6. Сосчитаем остаток продукции на складе фирмы:

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

· 50 - (8*2+4*5) =14 кг. - остаток ягод;

· 44 - (8*4+4*3)=0 кг. - остаток сахара;

· 36 - (8*4+4*1)=0 кг. - остаток воды.

Ответ: для того чтобы реализация от продажи было максимальным, фирме ежедневно нужно выпускать 8 килограмм клубничного варенья и 4 килограмма малинового. При таком выпуске продукции доход фирмы составляет 20 евро, при стоимости 1 килограмма клубничного варенья в 2 евро, а малинового - 1 евро. При этом на складе от суточного запаса продуктов, входящих в состав варенья остается: 14 килограмм ягод, 0 килограмм сахара и 0 килограмм воды.

Симплекс метод

Задача: рассматриваем условие предыдущей задачи.

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

Решение:

1. Составляем каноническую модель

2. Нулевой шаг. Составим симплекс таблицу

bi	x1	x2	x3	x4	x5
50	2	5	1	0	0
44	4	3	0	1
36	4	1	0	0	:4 *(-1) *(-0,5)
0	2	1	0	0	0



X⁰ = (0; 0; 50; 44; 36) - опорное решение

=0

Из последней строки выбираем наибольшее значение. Это число 2 ? х₁ - разрешающий столбец. Ищем минимальное значение в этом столбце.

Выбираем разрешающий элемент равный 4, получим новую симплекс таблицу.

3. Первый шаг

bi	x1	x2	x3	x4	x5
32	0	4,5	1	0	-0,5
8	0	2	0	1	-1	:2 *(-2,25) *(-0,125) *(-0,25)
9	1	0,25	0	0	0,25
-18	0	0,5	0	0	-0,5

X¹ = (9; 0; 32; 8; 0) - опорное решение

=18

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



Переводим х₂ в базис, получим новую симплекс таблицу.

4. Второй шаг.

bi	x1	x2	x3	x4	x5
14	0	0	1	-2,25	1,75
4	0	1	0	0,5	-0,5
8	1	0	0	-0,125	0,375
-20	0	0	0	-0,25	-0,25

X² = (8; 4; 14; 0; 0) - оптимальное решение

=20 (евро)

В последней строке нет положительный элементов. Следовательно, симплекс метод закончен.

Ответ: в ходе решения задачи симплекс методом получили оптимальное решение (8;4;14;0;0), где первые две цифры являются значением х₁ (количество килограмм клубничного варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) и х₂ (количество килограмм малинового варенья необходимое выпускать ежедневно фирме, при реализации которого она бы получала максимальный доход) соответственно, а остальные - это остаток сырья на складе. Так же получили значение =20 (евро), являющиеся максимальным доходом от реализации продукции.

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

линейный программирование графический транспортный

	ответ полученный графическим способом	ответ полученный симплекс методом
х1, кг	8	8
х2, кг	4	4
, евро	20	20
остаток ягод, кг	14	14
остаток сахара, кг	0	0
остаток воды, кг	0	0

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

Задача: рассматриваем условие первой задачи.

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

Решение:

1. Составим двойственную задачу из исходной (см. условие графической задачи). Для этого все матрицы исходной задачи транспонируются. При этом неравенство исходной системы имеют одинаковый знак (? или ?)

Исходная задача:

> max,

где х₁ и х₂ - количество килограмм каждого из варений.

Двойственная задача:

,

где - цена одного килограмма ягод, сахара и воды соответственно

- опорное решение двойственной задачи.

2. Имеем х₁=8 и х₂=4. Подставим их в ограничения исходной задачи и найдем строгое неравенство.

? ? _?- ?

=2

;

(евро)

Ответ: продавец согласен продать, а покупатель купить за 0,25 евро один килограмм сахара, за такую же цену килограмм воды, а килограмм ягод отдать бесплатно. При этом минимальные затраты на производство варенья составят 20 евро.

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

Проверка:

;

0,25=;

0,25=0,25;

;

0,25=;

0,25=0,25;

Транспортная задача

Задача: в порту стоят три рыболовецких судна А₁, А₂, А₃, вмещающих рыбу в количествах 125 тонн, 125 тонн и 105 тонн соответственно. Необходимо доставить свежо пойманную рыбу в пять магазинов, находящиеся от порта на 60, 65, 95, 35 и 100 километров соответственно. Стоимость перевозки одной тонны из судна А_i в магазин B_j заданы в виде матрицы.

C= ; A= ; B=

Найти: минимальные суммарные затраты на перевозку рыбы из суден в магазины.

Решение:

?

355=355 ? закрытая транспортная задача.

1. Метод северо-западного угла

	B1	B2	B3	B4	B5	запас
A1		8		7		15		2		4	125
	60	65	0
A2		2		10		23		7		18	125
			95	30
A3		24		15		6		9		35	105
				5	100
потребности	60	65	95	35	100	355

n+m-1=5+3-1=7

F - суммарные затраты на перевозку

F₁=

(рублей)

2. Метод наименьшей стоимости в таблице

	V1	V2	V3	V4	V5	запас
	B1	B2	B3	B4	B5
U1	A1		8		7		15		2		4	125
			0		35	90
U2	A2		2		10		23		7		18	125
		60	65
U3	A3		24		15		6		9		35	105
				95		10
потребности	60	65	95	35	100	355

n+m-1=5+3-1=7

F - суммарные затраты на перевозку

F₂=

(рублей)

3. Метод потенциалов

Проверим на оптимальность план, полученный во второй таблице.

	V1	V2	V3	V4	V5	запас
	B1	B2	B3	B4	B5
U1	A1		8		7		15		2		4	125
			0		35	90
U2	A2		2		10		23		7		18	125
		60	65
U3	A3		24		15		6		9		35	105
				95		10
потребности	60	65	95	35	100	355



1) Для занятых клеток

2) Для свободных клеток

Так как имеются нарушения, то проверяемый план не является оптимальным. Среди нарушений выбираем наибольшее и строим цикл перерасчета данной клетки. Наибольшим нарушением является

	V1	V2	V3	V4	V5	запас
	B1	B2	B3	B4	B5
U1	A1		8		7		15		2		4	125
			0		25	100
U2	A2		2		10		23		7		18	125
		60	65
U3	A3		24		15		6		9		35	105
				95	10
потребности	60	65	95	35	100	355



n+m-1=5+3-1=7

F - суммарные затраты на перевозку

F₃=

(рублей)

1) Для занятых клеток

2) Для свободных клеток

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

Ответ: в ходе решения задачи получили следующие данные:

§ минимальные суммарные затраты на перевозку

F₁ = 6875 рублей (метод северо-западного угла);

F₂ = 2120 рублей (метод наименьшей стоимости);

F₃ = 1880 рублей (метод потенциалов)

§ оптимальный план перевозок можно представить в виде матрицы

C=

Транспортная задача на сети

Задача: даны узлы (обозначены кругом или квадратом) и дуги (прямые, соединяющие узлы). На каждой дуге указывается длина или стоимость перевозки единицы груза. На каждой вершине показываются запасы груза со знаком «+» (склад - квадрат) и потребности в этом грузе со знаком «-» (потребители - круг).

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

Решение:

1. составим схему

2. Число загруженных дуг n-1, где n - количество вершин

n=10; 10 - 1 = 9 - загруженные дуги

3. Один из потенциалов выбираем произвольно. Пусть А₁=100. Далее двигаемся по загруженным дугам, если направление совпадает, то к известному потенциалу прибавляем значение указанное на дуге, если направление встречное - вычитаем.

4. Выполняем проверку по свободным дугам. Для этого из большего потенциала вычитаем меньший и полученную разность должна быть меньше либо равна расстоянию, указанного на дуге.

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

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

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

5. Суммарные затраты на перевозку считаются путем сложения произведения значения загруженной дуги на значение перевозки.



.

Ответ: оптимальный план перевозок представлен на схеме. При таком раскладе суммарные затраты на перевозку составляют

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