Министерство науки и образования Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра автоматизированных систем обработки информации
Расчётная работа №1
Графический метод решения задач линейного программирования
Выполнил: ст. гр. РС-05,
Паляруш А.Б.
Проверил:
Доцент кафедры АСОИ
Саликов В.А
Г. Днепропетровск
2007 г.
Постановка задачи
Для производства двух видов продукции А и В предприятие использует 4 группы оборудования (1, 2, 3, 4) на производство одной штуки продукции А требуется занять в течение рабочей смены 1, 0, 5 и 3 единиц соответственно 1, 2, 3, 4 оборудования, а на производство одной штуки продукции В требуется 1, 1, 0, 2 единиц оборудования 1, 2, 3, 4. Имеется оборудование по группам 1 – 18, 2 – 12, 3 – 24, 4 – 18 единиц. Предприятие получает с одной штуки продукции А 4 гривны чистого дохода и 6 гривен - с одной штуки продукции В.
Сколько штук продукции каждого вида должно производить предприятие, чтобы получить наибольшую прибыль?
Группа оборудования, штук для производства единицы продукции |
Прибыль, грн |
1 |
2 |
3 |
4 |
А |
1 |
0 |
5 |
3 |
4 |
В |
1 |
1 |
0 |
2 |
6 |
Построение математической модели
Для реализации графического метода решения задач линейного программирования необходимо определить целевую функцию:
Z=4*x1+6*x2, где Z→max – целевая функция,
x1 – количество изготовленной продукции вида А,
x2 – количество изготовленной продукции вида В.
Далее необходимо определить ограничения, задающие ОДР:
(1) x1+ x2 ≤ 18; вытекает из доступного количества оборудования первой группы
(2) x2 ≤ 12; вытекает из доступного количества оборудования второй группы
(3) 5*x1 ≤ 24; вытекает из доступного количества оборудования третей группы
(4) 2*x1+2*x2 ≤ 18;вытекает из доступного количества оборудования четвёртой группы
(5) x1 ≥ 0;условие неотрицательности;
(6) x2 ≥ 0 ; условие неотрицательности;
Построим все полученные ограничения и целевую функцию:
Теперь можно увидеть, что ОДР ограничена (4) x1+x2 ≤ 9, (3) x1 ≤ 4.8, x1 ≤ 0, x2≤ 0.
Наилучшее (оптимальное) решение отмечено красным крестиком. Максимальная прибыль достигается в точке (0, 9), А=0, В=9; при нахождении оптимального решения данной задачи следует помнить, что количество продукции (равно как и количество ресурса) целое число.
Z(0,9)=4*0+9*6=54 (грн).
Чувствительность модели
Благодаря исследованию чувствительности модели, мы получаем информацию о ценности ресурса.
Оборудование группы 1 (голубой цвет на графике) не является дефицитным и не влияет на оптимальную точку т.к. вышло далеко за ОДР, его очень много. Это оборудование станет дефицитным при уменьшении его количества на 9 единиц.
Оборудование группы 2 (зелёный цвет на графике) так же не является дефицитным, однако, при уменьшении его количества на 3 единицы оно начнёт влиять на результат.
Оборудование группы 3 (синий цвет на графике) не дефицитно. Изменяя его количество, при неизменном количестве других ресурсов, мы не повлияем на результат т.к. для производства продукции А (именно она должна производиться для максимальной прибыли) его расход равен 0.
Оборудование группы 4 (чёрный цвет на графике) является дефицитным, ценность данного ресурса можно определить, увеличив его количество на 2 единицы (т.к. именно столько необходимо для производства одной единицы продукции А):
Следовательно, при изменении количества ресурса 4 на единицу прибыль растёт на 3 гривны. Данный ресурс можно увеличивать до 24 единиц, потом он перестанет быть дефицитным, значит, не будет влиять на оптимальное решение.
Другие работы по теме:
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
Метод ветвей и границ (контрольная)
Министерство образования Р.Ф. Тюменский государственный нефтегазовый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭК Контрольная работа по
Теория информации. Статистический подход
Статистический подход к измерению правовой информации. Графический метод решения задач линейного программирования. Методика решения задач линейного программирования графическим методом. Количество информации как мера неопределенности состояния системы.
Риск в задачах линейного программирования
Лабораторная работа №3 Риск в задачах линейного программирования. Задание: Предприятие выпускает 2 вида продукции в объмах Н1 и Н2. Известен случайный вектор ограничений -
Решение задачи линейного программирования
Рассмотрим задачу линейного программирования Теорема . Если множество планов задачи (1) не пусто и целевая функция сверху ограничена на этом множестве, то задача (1) имеет решение.
Задача линейного программирования
Юридический техникум Рассмотрено и одобрено ПЦК г. Кропоткин программирования Председатель ПЦК Покалицына О.В. План чтения лекции по учебной дисциплине
Задачи по Математике 3
Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции F=2x1 + x2 max min 2X1 + X2 ≥ 4 2X1 - X2 ≤ 0 0 ≤ X1 < 2 0 ≤ X2 < 8 Решение:
Симплекс метод в форме презентации
Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
Линейное программирование 3
БАЛТИЙСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ РЫБОПРОМЫСЛОВОГО ФЛОТА РФ ИНСТИТУТ ПРИКЛАДНОЙ ЭКОНОМИКИ И МЕНЕДЖМЕНТА КАФЕДРА «МЕНЕДЖМЕНТ» Контрольная работа
Математические методы методы
Общая задача линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции
Симплекс метод решения задачи линейного программирования
Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
Регрессионные зависимости
Вычисление значений регрессионно-авторегрессионной зависимости заданного выражения линейного программирования. Графическое представление математической модели в виде уравнения регрессии. Принципи оптимизации производственных и коммерческих операций.
Графический метод решения задач линейного программирования
Графический метод как наиболее простой и наглядный метод линейного программирования, его сущность и содержание, особенности применения на современном этапе. Этапы реализации данного метода. Описание интерфейса разработанного программного продукта.
Решение задачи оптимального управления
Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
Решение задач линейного программирования
Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
Введение в программирование
Сущность отладки, условия ее выполнения. Ошибки при компиляции программы, создание и изменение исходных символьных файлов. Процесс преобразования кода в машинный. Первый программист, виды трансляторов, классификация и уровни языков программирования.
Алгоритмы численного решения задач
Графоаналитический метод решения задач. Получение задачи линейного программирования в основном виде. Вычисление градиента и поиск экстремумов методом множителей Лагранжа. Параболоид вращения функции. Поиск решения на основе условий Куна-Таккера.
Задач линейного программирования
Цель работы: изучить теорию и методы решения задач линейного программирования; пробрести навыки построения моделей линейного программирования и решения задач линейного программирования на ЭВМ.
Эффективное распределение ресурсов, транспортная задача
Доклад на тему «Эффективное распределение ресурсов. Транспортная задача.» В настоящее время большое прикладное значение имеет задача распределения ресурсов по работам. Значение этой проблемы определяется, во-первых, ограниченностью ресурсов и, во-вторых, тем, что эффективность ресурсов в разных направлениях может быть различна.
Построение и анализ на чувствительность моделей задач линейного программирования
Лабораторная работа №1 ПОСТРОЕНИЕ И АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: научиться определять оптимальный план производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида; освоить методику и технологию поиска оптимального решения задач линейного программирования (ЗЛП) с помощью ЭВМ; приобрести практический опыт проведения анализа оптимального решения ЗЛП на чувствительность.
Анализ безубыточности
Графический метод Для определения безубыточного объема продаж также используют и графический метод (рис. ). Рис. График безубыточности По горизонтали показывается объем реализации продукции в процентах от производственной мощности предприятия, или в натуральных единицах (если выпускается один вид продукции), или в денежной оценке (если график строится для нескольких видов продукции), по вертикали- себестоимость проданной продукции и прибыль, которые вместе составляют выручку от реализации.