Графический метод решения задачи линейного программирования
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
чи
Пусть х1, х2, х3, х4 - число единиц изделий А, Б, В и неокрашенные В. Тогда целевая функция задачи:
W = 25x1+20x2+50x3+30x4 max.
Ограничения по трудовым ресурсам.
3х1 + х2 + 4х3 + 4х4 100
х1 + 2х2 + 5х3 + 5х4 100
х1 + 5х2 + 4х3 100
Переменные имеют неотрицательные значения:
х10, х20, х30, х40.
Целевая функция двойственной задачи к исходной:
WДВ = 100z1 +100z2 +100z3 min,
где Zi, (i = 1,3) - двойственные оценки ресурсов.
Ограничения:
z1 +4z2 +5z3 25
z1 +2z2 +5z3 20
z1 +5z2 +4z3 50
z1 +5z2 30
Переменные имеют неотрицательные значения:
z10, z20, z30.
) Решение симплекс методом
Для обращения системы ограничений-неравенств в систему уравнений прибавим к левой части каждого неравенства добавочные неотрицательные переменные x5, x6, x7. Эти добавочные переменные в условиях данной задачи имеют конкретное экономическое содержание, а именно: объем остатков сырья каждого вида после выполнения плана выпуска продукции.
х1 + х2 + 4х3 + 4х4+х5 100
х1 + 2х2 + 5х3 + 5х4 +х6 100
х1 + 5х2 + 4х3+х7 100
хi0, (i=1,2.7).
После введения добавочных переменных получим систему уравнений: Нужно найти такое допустимое базисное решение системы, которое бы максимизировало целевую функцию F, т.е. необходимо найти оптимальное решение задачи. Так как система ограничений состоит из трех независимых уравнений с семью переменными, то число основных (базисных) переменных должно равняться трем, а число неосновных - четырем. Для решения задачи симплексным методом, прежде всего, нужно найти любое базисное решение. В условиях данной задачи оно может быть найдено без труда. Для этого достаточно принять за основные добавочные переменные x5, x6, x7. Так как коэффициенты при этих переменных образуют единичную матрицу, то отпадает необходимость вычислять определитель (определитель единичной матрицы равен 1, т.е. отличен от нуля). Основные переменные x5, x6, x7. Составляем первую симплекс-таблицу. Находим разрешающий элемент.
-просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки (исключая столбец свободных членов ) выбирается наименьшее отрицательное число при отыскании max, либо наибольшее положительное при задачи на min. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;
-просматривается столбец таблицы, отвечающий выбранному отрицательному (положительному) коэффициенту в последней строке - ключевой столбец, и в этом столбце выбираются положительные коэффициенты. Если таковых нет, то целевая функция неограниченна на области допустимых значений переменных и задача решений не имеет;
-среди выбранных коэффициентов столбца выбирается тот, для которого абсолютная величина отношения соответствующего свободного члена (находящегося в столбце свободных членов) к этому элементу минимальна. Этот коэффициент называется разрешающим, а строка, в которой он находится ключевой;
Базисные переменныеСвоб. членыХ1Х2Х3Х4Х51003144Х61004255Х71005540F0-25-20-50-30
Разделим каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения запишем в строку с измененной базисной переменной новой симплекс таблицы.
-в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.
-столбец, у которого в ключевой строке имеется 0, в новой таблице будет таким же.
-строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.
Базисные переменныеСвоб. членыХ1Х6Х3Х4Х520-1/5-3/500Х3204/52/511Х720117/50-4F1000150020
Так как в строке F нет отрицательных элементов, то найдено оптимальное решение F=1000, при значениях переменных равных: X3=20.
2.3 Решения задачи в MS Excel
Так как переменные задачи входят в целевую функцию и ограничения задачи линейно, то соответствующая задача оптимизации является задачей линейного программирования и для её эффективного решения можно применить приложение MS Excel.
. Создаем форму для ввода условий задачи (рисунок 2.1). Вводим исходные данные и зависимости из математической модели.
Рисунок 2.1 - Форма ввода данных
. Назначение целевой функции. Вызвать меню: Данные, Поиск решения. Заполнить форму поиска решения (рисунок 2.2).
Рисунок 2.2 - Поиск решения
. Результат поиска решения.
Рисунок 2.3 - Результат поиска решения задачи
Анализ задачи:
Внутренняя структура решения задачи в Excel может быть проанализирована с помощью 3-х отчетов:
.Отчет по результатам.
2.Отчет по устойчивости.
.Отчет по пределам.
Рисунок 2.4 - Отчет по результатам
Из отчета по результатам видно, что для получения максимальной прибыли в размере 1000 усл. ед. необходимо производить 20 единиц изделия В.
ресурс расходуется полностью, т.е. является дефицитным.
Рисунок 2.5 - Отчет по устойчивости
Теневая цена - это удельная прибыль, т.е. размер дополнительной прибыли, которую можно получить, увеличив запас ресурса на один. Так как запас ресурса равен 100, а увеличение его на один процент равен 101, т.е. на один, то можно считать, что при увеличении трудовых ресурсов на 1% произойдет увеличение прибыли на 10 усл. ед. (значение теневой