Контрольная работа по " Методы оптимальных решений"

Министерство образования Российской  федерации

Федеральное государственное образовательное  бюджетное учреждение

высшего профессионального образования

«Хабаровская государственная  академия экономики и права»

Центр по работе с филиалами и  дистанционному обучению

 

 

 

 

Кафедра: Математики и математических методов в экономике

 

 

Контрольная работа

по дисциплине: Методы оптимальных решений

Вариант № 1

 

Выполнил(а):	Воронина  Наталья Борисовна
Курс:	4
Группа:	БУ(ДБС)-11 080109
Специальность:	Бухгалтерский учет анализ и аудит
Зачетная книжка №:	1101271
Адрес электронной почты:	_-natali-_80@mail.ru
Контактный телефон:	+8(914)2839009

 

 

 

 

Хабаровск  2013

 

 

Содержание

 

1 Симплексный метод в линейном программировании задачи         контрольной работы № 1	3
2    Двойственность в линейном программировании задачи контрольной работы № 2	7
3    Транспортная задача  задачи контрольной работы № 3	9
4    Сетевое планирование и управление. Расчёт основных показателей    задачи контрольной работы № 4	12
Список литературы	14

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Симплексный метод в линейном программировании

Задачи  контрольной работы № 1

Предположим, что для производства двух видов продукции А и В можно использовать сырьё трёх видов. При этом на изготовление единицы изделия А расходуется 4 ед. сырья первого вида, 2 – ед. 2-го и 3 – 3-го вида. На изготовление единицы изделия В расходуется 2ед. сырья 1-го вида, 5–ед. 2-говида, 4–ед. 3-го вида сырья. На складе фабрики имеется сырья 1-говида 35ед., 2-го–43, 3-го–40ед. От реализации единицы готовой продукции фабрика имеет прибыль 5тыс.руб.,а от продукции В прибыль составляет 9 тыс. руб.

Составить математическую модель исходной задачи. Найти решение  симплексным методом и графически.

Решение:

Пусть x₁ – число единиц продукции A, а x₂ – число единиц продукции B. Тогда математическая модель задачи примет вид:

Решим поставленную задачу графически. В первую очередь, найдем область допустимых значений, т.е. точки x₁ и x₂, которые удовлетворяют системе ограничений. По условию задачи x₁³0, x₂³0 ,т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.

Заменим знак неравенства  на знак равенства: . Рассчитаем две точки:

• при х₁ = 0, x₂ = 17,5;
• при х₂ = 0, x₁ = 8,75.

Заменим знак неравенства  на знак равенства: . Рассчитаем две точки:

• при х₁ = 0, x₂ = 8,6;
• при х₂ = 0, x₁ = 21,5.

Заменим знак неравенства  на знак равенства: . Рассчитаем две точки:

• при х₁ = 0, x₂ = 10;
• при х₂ = 0, x₁ = 13¹/₃.

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

 

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

Обозначим границы  области многоугольника решений.

Рассмотрим  целевую функцию задачи F = 5x₁+9x₂ → max.

Построим прямую, отвечающую значению функции F = 0: F = 5x₁+9x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений представляет собой многоугольник

Прямая F(x) пересекает область в точке C. Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему  уравнений, получим: x₁ = 4, x₂ = 7. Откуда найдем максимальное значение целевой функции:

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

Для построения первого опорного плана систему неравенствприведем систему к канонической форме.

Решим систему  уравнений относительно базисных переменных: x₃, x₄, x₅.

Полагая, что свободные  переменные равны 0, получим первый опорный план:X₁ = (0,0,35,43,40).

 

Базис	B	x1	x2	x3	x4	x5
x3	35	4	2	1	0	0
x4	43	2	5	0	1	0
x5	40	3	4	0	0	1
F(X0)	0	-5	-9	0	0	0

 

Переходим к  основному алгоритму симплекс-метода.

Текущий опорный  план неоптимален, так как в индексной  строке находятся отрицательные  коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем  наименьшее. Следовательно, 2-ая строка является ведущей.

Разрешающий элемент  равен (5) и находится на пересечении ведущего столбца и ведущей строки.

Аналогично  выполним все остальные шаги.

Базис	B	x1	x2	x3	x4	x5	min
x3	35	4	2	1	0	0	171/2
x4	43	2	5	0	1	0	83/5
x5	40	3	4	0	0	1	10
F(X1)	0	-5	-9	0	0	0	0
x3	174/5	31/5	0	1	-2/5	0	59/16
x2	83/5	2/5	1	0	1/5	0	211/2
x5	53/5	12/5	0	0	-4/5	1	4
F(X2)	772/5	-12/5	0	0	14/5	0	0
x3	5	0	0	1	13/7	-22/7
x2	7	0	1	0	3/7	-2/7
x1	4	1	0	0	-4/7	5/7
F(X3)	83	0	0	0	1	1

Индексная строка не содержит отрицательных элементов - найден оптимальный план

Оптимальный план можно записать так:

x₂ = 7;  x₁ = 4

 
 2. Двойственность в линейном программировании

      Задачи контрольной работы № 2

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

Решение: Составим двойственную задачу к прямой задаче.

Решение двойственной задачи дает оптимальную систему  оценок ресурсов.Используя последнюю  итерацию прямой задачи найдем, оптимальный  план двойственной задачи. Из теоремы двойственности следует, что . Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

 

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.Тогда

Оптимальный план двойственной задачи равен:

y₁ = 0  y₂ = 1  y₃ = 1

Значение целевой  функции двойственной задачи совпадает  с решением прямой задачи. Следовательно, решение найдено верно. 
 3. Транспортная задача 

      Задачи контрольной работы № 3

 

Требуется найти план перевозок  однородного груза изпунктовА₁,...,А_m, содержащих соответственно а₁,а₂,... ,а_m единиц груза, в пункты В₁, В₂, ... , В_n в количествах b₁, b₂, ... , b_n соответственно, при котором суммарные транспортные затраты будут наименьшими.

Известны с_ij – затраты на перевозку 1 единицы груза из пункта А_i и B_j.

 

	B1	B2	B3	B4	B5	Запасы
A1	8	3	5	6	4	210
A2	5	10	4	8	7	250
A3	4	4	5	7	3	200
A4	6	8	7	6	2	290
Потребности	150	210	170	220	200

 

Решение:

Проверим необходимое  и достаточное условие разрешимости задачи:

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

	B1	B2	B3	B4	B5	Запасы
A1	8[150]	3 [60]	5	6	4	210
A2	5	10 [150]	4 [100]	8	7	250
A3	4	4	5 [70]	7 [130]	3	200
A4	6	8	7	6 [90]	2 [200]	290
Потребности	150	210	170	220	200

 

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

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

Значение целевой  функции для этого опорного плана  равно:

Проверим оптимальность  опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

	v1=8	v2=3	v3=-3	v4=-1	v5=-5
u1=0	8[150]	3[60]	5	6	4
u2=7	5	10[150]	4[100]	8	7
u3=8	4	4	5[70]	7[130]	3
u4=7	6	8	7	6[90]	2[200]