Графический метод решения задач линейного программирования
Расчет производства необходимого количества продукции для получения максимальной прибыли предприятия. Математическая модель для решения задач линейного программирования. Построение ограничений и целевых функций. Исследование чувствительности модели.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 21.08.2010 |
| Размер файла | 74,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство науки и образования Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра автоматизированных систем обработки информации
Расчётная работа №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 единиц, потом он перестанет быть дефицитным, значит, не будет влиять на оптимальное решение.
Подобные документы
Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Строение системы уравнений-ограничений и ее переменных, графический способ решения задач линейного программирования на плоскости. Выражение неизвестных через две независимые переменные, являющиеся координатными осями графика. Значение целевой функции.
лабораторная работа [61,4 K], добавлен 07.01.2011Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Графический метод как наиболее простой и наглядный метод линейного программирования, его сущность и содержание, особенности применения на современном этапе. Этапы реализации данного метода. Описание интерфейса разработанного программного продукта.
контрольная работа [318,0 K], добавлен 11.06.2011Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011
