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

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

Модуль 1

Выполнила студентка группы 1-Б52ЭК/21 Родина Юлия Алексеевна

 

ЗАДАНИЕ 1.

 Тема: Прямая задача линейного программирования.

 

Фирма производит и продает два типа товаров. Фирма получает прибыль в размере 14 тыс.р. от производства и продажи каждой единицы товара 1 и в размере 5 тыс.р. от производства и продажи каждой единицы товара 2. Фирма состоит из трех подразделений. Затраты труда (чел-дни) на производство этих товаров в каждом из подразделений указаны в таблице.

 

Таблица 1

Подразделение	Трудозатраты, чел-дней на 1 шт.
	товар 1	товар 2
1	1	3
2	2	3
3	2	2

 

 Руководство рассчитало, что  в следующем месяце фирма будет  располагать следующими возможностями обеспечения производства трудозатратами: 900 чел-дней в подразделении 1, 1000 — в подразделении 2 и 1600 — в подразделении 3. Составить задачу линейного программирования и найти ее решение.

Решение.

Решим задачу, используя симплекс-таблицу.

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

 

 

Приведем задачу к каноническому виду путем введения дополнительных переменных . В целевую функцию эти переменных входят с нулевыми коэффициентами:

 

 

 

Таблица 2

Базисные переменные	Свободные члены	Переменные					Оценочные соотношения①
	900	1	3	1	0	0
	1000		3	0	1	0
	1600	2	2	0	0	1
	0	-14	-5	0	0	0
		s=1
Базисные переменные	Свободные члены	Переменные					Оценочные соотношения
	400	0		1		0
	500	1		0		0
	600	0	-1	0	-1	1
	7000	0	16	0	7	0

 

1) переносим значения коэффициентов  при неизвестных в симплексную  таблицу.

2) анализируем строку . Так как в ней есть отрицательные элементы, то выбираем наибольший по модулю из отрицательных. Это значение равно -14, этот столбец и будет разрешающим s=1 (так как этот столбец соответствует переменной ).

3) составляем оценочные соотношения, используя правила. Так как значения свободных членов и коэффициентов, стоящих в разрешающем столбце, имеют одинаковые знаки, то используем правило №5.

4) выбираем разрешающую строку. Для нашего случая – это  строка, соответствующая переменной , поэтому q=4.

5) на пересечении разрешающих  столбца и строки стоит элемент  равный 2, который называется разрешающим.

6) далее переходим к новой  таблице:

• записываем новый базис, где вместо будет ;
• применяем правило для всех базисных переменных если
• сравниваем индексы столбца Базисных переменных и строки Переменные.

 на пересечении  стоит коэффициент  т.к.

 не является базисным, это правило мы не используем;

            на пересечении стоит коэффициент т.к.

 не является базисным, это правило мы не используем;

 на пересечении  стоит коэффициент  т.к.

• аналогично делаем для остальных базисных переменных.
• далее определяем строку, в которой происходила замена базиса. Берем старую строчку, где q=4 и делим её на разрешающий элемент, в нашем случае на 2.
• в строке для всех базисных переменных пишем «нуль».
• Далее используем правило «прямоугольника». Учитываются только значения, которые стоят на вершинах.

Для первой строки получаем:

 

Для третьей строки получаем:

 

Для последней строки получаем:

 

 

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

Получены следующие значения

 

Если какие-то переменные отсутствуют в Базисных переменных, то они равны нулю,  например,

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

Подставим оптимальные значения в ограничения КЗЛП:

 

Получим, что общий фонд рабочего времени оборудования используется полностью для B оборудования, а для A и C имеет в избытке:

 

Таким образом, основные переменные обозначают количество продукции каждого вида, а дополнительные переменные – объем недоиспользованных ресурсов.

Ответ. Для получения максимальной прибыли необходимо изготовить ед. продукции 1 и ед. продукции 2. При этом имеются в излишках станко-час для оборудования типа А и 600 станко-час для оборудования типа C.

 

ЗАДАНИЕ  2.

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

 

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

Переменные

 двойственная  оценка группы оборуд.A

 двойственная  оценка группы оборуд.B

 двойственная  оценка группы оборуд.C

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

 

Ограничения:

 

Воспользуемся соотношением (6.2.1) второй теоремы двойственности:

 

тогда

 

 

 

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

 

 

 

или

 

 

 

Воспользуемся соотношением (6.2.2) второй теоремы двойственности:

 

В нашей задаче и, поэтому оба неравенства двойственной задачи обращаются в равенство:

 

Решая полученную систему уравнений, находим теневые цены:

 

Проверим выполнение первой теоремы двойственности:

 

 

 

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

 

Первая теорема двойственности выполняется и это означает, что оптимальный план двойственной задачи определен верно.

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