Автор работы: Пользователь скрыл имя, 11 Марта 2014 в 22:52, контрольная работа
Задача № 1
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решить задачу на максимум, и почему?
Условие задачи:
Имеется два вида корма I и II, содержащие питательные вещества (витамины) , и . Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице.
Питательное вещество (витамин) Необходимый минимум питательных веществ Число единиц питательных
Веществ
в 1 кг корма
I II
9 3 1
8 1 2
12 1 6
Стоимость 1 кг корма I и II соответственно равна 4 и 6 ед.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание питательных веществ каждого вида было бы не менее установленного предела.
Задача № 2
Для изготовления двух видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице 24.
Таблица 24 – Исходные данные к задаче
Тип сырья Нормы расхода сырья на одно изделие, ед. Запасы сырья, ед.
А Б
I 1 2 11
II 2 1 5
III 1 3 14
Прибыль изделия, ден. ед. 4 2 Х
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
1 Условные обозначения, применяемые при моделировании 3
2 Задача № 1 9
3 Задача № 2 12
4 Задача № 3 17
Список используемой литературы 28
Решим систему из двух уравнений ограничений, которые дали искомую точку.
,
;
,
(ден. ед.)
Т.о. оптимальное решение найдено. Минимум расходов 26 ден. ед. достигается при использовании 2 единиц I вида корма и 3 единиц II вида питательных веществ.
3 Задача № 2
Для изготовления двух видов продукции используют три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице 24.
Таблица 24 – Исходные данные к задаче
Тип сырья |
Нормы расхода сырья на одно изделие, ед. |
Запасы сырья, ед. | |
А |
Б | ||
I |
1 |
2 |
11 |
II |
2 |
1 |
5 |
III |
1 |
3 |
14 |
Прибыль изделия, ден. ед. |
4 |
2 |
Х |
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 4x1 + 2x2 при следующих условиях-ограничений.
x1 + 2x2≤11
2x1 + x2≤5
x1 + 3x2≤14
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 11
2x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5
1x1 + 3x2 + 0x3 + 0x4 + 1x5 = 14
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,11,5,14)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
11 |
1 |
2 |
1 |
0 |
0 |
x4 |
5 |
2 |
1 |
0 |
1 |
0 |
x5 |
14 |
1 |
3 |
0 |
0 |
1 |
F(X0) |
0 |
-4 |
-2 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (11 : 1 , 5 : 2 , 14 : 1 ) = 21/2
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
min |
x3 |
11 |
1 |
2 |
1 |
0 |
0 |
11 |
x4 |
5 |
2 |
1 |
0 |
1 |
0 |
21/2 |
x5 |
14 |
1 |
3 |
0 |
0 |
1 |
14 |
F(X1) |
0 |
-4 |
-2 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (2), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
11-(5 • 1):2 |
1-(2 • 1):2 |
2-(1 • 1):2 |
1-(0 • 1):2 |
0-(1 • 1):2 |
0-(0 • 1):2 |
5 : 2 |
2 : 2 |
1 : 2 |
0 : 2 |
1 : 2 |
0 : 2 |
14-(5 • 1):2 |
1-(2 • 1):2 |
3-(1 • 1):2 |
0-(0 • 1):2 |
0-(1 • 1):2 |
1-(0 • 1):2 |
0-(5 • -4):2 |
-4-(2 • -4):2 |
-2-(1 • -4):2 |
0-(0 • -4):2 |
0-(1 • -4):2 |
0-(0 • -4):2 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
81/2 |
0 |
11/2 |
1 |
-1/2 |
0 |
x1 |
21/2 |
1 |
1/2 |
0 |
1/2 |
0 |
x5 |
111/2 |
0 |
21/2 |
0 |
-1/2 |
1 |
F(X1) |
10 |
0 |
0 |
0 |
2 |
0 |
1. Проверка критерия
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x3 |
81/2 |
0 |
11/2 |
1 |
-1/2 |
0 |
x1 |
21/2 |
1 |
1/2 |
0 |
1/2 |
0 |
x5 |
111/2 |
0 |
21/2 |
0 |
-1/2 |
1 |
F(X2) |
10 |
0 |
0 |
0 |
2 |
0 |
Оптимальный план можно записать так:
x1 = 21/2
F(X) = 4•21/2 = 10
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 81/2
В оптимальный план вошла дополнительная переменная x5. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 111/2
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
В индексной строке в 2-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Покажем это на примере. Свободную переменную, соответствующую указанному столбцу, вносим в базис (вместо x3), выполнив соответствующие этапы алгоритма.
После преобразований получаем новую таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x2 |
52/3 |
0 |
1 |
2/3 |
-1/3 |
0 |
x1 |
-1/3 |
1 |
0 |
-1/3 |
2/3 |
0 |
x5 |
-22/3 |
0 |
0 |
-12/3 |
1/3 |
1 |
F(X ) |
10 |
0 |
0 |
0 |
2 |
0 |
В результате получен второй оптимальный план с другим набором базисных переменных.
В индексной строке в 3-ом столбце нулевое значение. В столбце, содержащем этот нуль, имеется хотя бы один положительный элемент. Следовательно, задача имеет множество оптимальных планов.
Информация о работе Контрольная работа по предмету "Экономико-математическое моделирование"