Решения задач линейного программирования
Составление математической модели задачи линейного программирования. Особенность проведения вычислений графическим методом. Расчет экономико-математической модели с помощью поиска проблем в среде Microsoft Excel. Анализ полученных оптимальных решений.
| Рубрика | Экономико-математическое моделирование |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 02.02.2015 |
| Размер файла | 630,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
1. Составить математическую модель следующей задачи линейного программирования
2. Решить графическим методом задачу линейного программирования
3. Технология решения задач линейного программирования с помощью Поиска решений в среде EXCEL
4. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений
1. Составить математическую модель следующей задачи линейного программирования
5) На фабрике производятся товары А и В. Данные о временных затратах на их производство и о прибыли от продажи единицы товара в таблице. В течение недели токарный станок может работать не более 70 часов, фрезерный - не более 40, а на завершающие операции дается не более 90 часов. Сколько продукции обоих типов следует выпускать в неделю для получения максимальной прибыли?
|
Время работы |
А |
В |
|
|
Токарный станок |
2 часа |
1 час |
|
|
Фрезерный станок |
1 час |
1 час |
|
|
Завершающие операции |
1 час |
3 часа |
|
|
Прибыль (за ед.) |
4 у.е. |
6.у.е. |
Введем следующие обозначения, x - Товар А, y - Товар B. Прибыль от реализации товара A - 4x а от реализации товара B - 6y, те. Необходимо максимизировать целевую функцию
4x+6y-> max
2x+y<=70
x+y<=40
x+3y<=90
x,y>=0
2. Решить графическим методом задачу линейного программирования
Введем следующие обозначения, x - Товар А, y - Товар B. Прибыль от реализации товара A - 4x а от реализации товара B - 6y, те. Необходимо максимизировать целевую функцию
Модель задачи
F(x)= 4x+6y-> max
Ограничения имеют вид:
2x+y<=70
x+y<=40
x+3y<=90
x,y>=0
Первое ограничение по токарному станку
2х1 + y 70
Прямая х1 + х2 = 70 проходит через точки (70, 0) и (0, 70).
Рис 1. Решением первого неравенства является нижняя полуплоскость
Второе ограничение по фрезерному станку х + y 40. Прямая х + y = 40 проходит через точки (40, 0) и (0, 40). Третье ограничение по завершающей операции х + 3у 90. На рис.2. заштрихована область допустимых решений.
Рис. 2. заштрихована область допустимых решений.
Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.
= (4;6)
Что бы построить этот вектор, нужно соединить точку (4;6) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации -- в противоположном направлении.
В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. в крайней, угловой точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума:
x + y = 40
x + 3y = 90.
Отсюда легко записать решение исходной ЗЛП: max f(x) = 210 и достигается при x=15 и y=25 (рис. 3.)
Рис. 3. Максимум целевой функции достигается в точке (15, 25).
3. Технология решения задач линейного программирования с помощью Поиска решений в среде EXCEL
Рассмотрим технологию решения используя условия Задачи 1.
Сформулируем экономико-математическую модель задачи.
Введем следующие обозначения, x - Товар А, y - Товар B. Прибыль от реализации товара A - 4x а от реализации товара B - 6y, те. Необходимо максимизировать целевую функцию
Модель задачи
F(x)= 4x+6y-> max
Ограничения имеют вид:
2x+y<=70 - ограничения по токарному станку
x+y<=40 - ограничения по фрезерному станку
x+3y<=90 - ограничения по завершающим операциям
x,y>=0 - ограничения по костюмам.
Решение.
1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). задача линейный программирование графический
Обозначим через x, y количество товаров каждого типа. В нашей задаче оптимальные значения вектора Х =(x, y,) будут помещены в ячейках A2:B2, оптимальное значение целевой функции в ячейке C3.
2. Ввести исходные данные.
Введем исходные данные задачи. В результате получим (Рисунок 3.1):
Рисунок 4 Данные ведены
3. Введем зависимость для целевой функции
· Курсор в ячейку «С3».
· Курсор на кнопку «Мастер функций», расположенную на панели инструментов.
· М1. На экране появляется диалоговое окно «Мастер функций шаг 1 из 2»
· Курсор в окно «Категория» на категорию «Математические».
· Курсор в окно «Функции» на «СУММПРОИЗВ» (рис.3.2).
Рис 5
На экране появляется диалоговое окно «СУММПРОИЗВ»
Рис. 6
· В строку «Массив 1» ввести А2:В2
· В строку «Массив 2» ввести А3:В3.
Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку.
На экране: в ячейку С3 введена функция.
Рис. 7
4. Введем зависимости для ограничений.
· Курсор в ячейку «С3».
· На панели инструментов кнопка «Копировать в буфер».
· Курсор в ячейку «С4».
· На панели инструментов кнопка «Вставить из буфера».
· Курсор в ячейку «С5».
· На панели инструментов кнопка «Вставить из буфера».
· Курсор в ячейку «С6».
· На панели инструментов кнопка «Вставить из буфера».
Рис. 8
Запуск поиска решений «Поиск решения».
Рисунок 9 «Поиск решения»
5. Назначить целевую функцию (установить целевую ячейку), указать адреса изменяемых ячеек.
· Курсор в строку «Установить целевую ячейку».
· Вводим адрес ячейки «$С$3».
· Вводим направление целевой.
· Курсор в строку «Изменяя ячейки».
· Вводим адреса искомых переменных А$2:В$2. (Рисунок 3.7)
Рисунок 10
6. Введем ограничения
· Указатель мышки на кнопку «Добавить. Появляется диалоговое окно «Добавление ограничения»
· В строке «Ссылка на ячейку» вводим адрес $С$4.
· Ввести знак ограничения ?.
· В строке «Ограничение» вводим адрес $D$4 (Рисунок 3.8)
· Указатель мышки на кнопку «Добавить». На экране вновь диалоговое окно «Добавление ограничения».
· Вводим остальные ограничения задачи, по выше описанному алгоритму
· После введения последнего ограничения кнопка «ОК».
На экране появится диалоговое окно «Поиск решения» с введенными условиями (Рисунок3.9).
Рисунок 11
Рисунок 12
7. Введем параметры для решения ЗЛП
В диалоговом окне указатель мышки на кнопку «Параметры». На экране появляется диалоговое окно «Параметры поиска решения».
Рис. 13
Устанавливаем флажки в окнах «Линейная модель» и «Неотрицательные значения».
· Указатель мышки на кнопку «ОК». На экране диалоговое окно «Поиск решения».
· Указатель мышки на кнопку «Выполнить».
Через непродолжительное время появится диалоговое окно «Результаты поиска решения» и исходная таблица с заполненными ячейками А3:В3 для значений Хi и ячейка С3 с максимальным значением целевой функции.
Рисунок 14
Указываем тип отчета «Устойчивость», и получаем дополнительную информацию об оптимальном решении.
Рис 3.12
В результате решения задачи получили ответ:
x = 15 - необходимо произвести товара A,
y = 25 - необходимо Произвести товара B,
F(x) = 210 что бы получить максимальную прибыль.
4. Двойственность в задачах линейного программирования. Анализ полученных оптимальных решений
Решение
1) Экономико-математическая модель исходной задачи.
= 4x+6y-> max
Ограничения имеют вид:
2x+y<=70 - ограничения по токарному станку
x+y<=40 - ограничения по фрезерному станку
x+3y<=90 - ограничения по завершающим операциям
x,y>=0 - ограничения по костюмам.
|
4 |
6 |
|||
|
Y1 |
2 |
1 |
70 |
|
|
Y2 |
1 |
1 |
40 |
|
|
Y3 |
1 |
3 |
90 |
Экономико-математическая модель двойственной задачи.
Y1 - Двойственная оценка токарного станка.
Y2 - Двойственная оценка фрезерного станка.
Y3 - Двойственная оценка завершающей операции.
g =70Y1+40 Y2 +90 Y3-> min
2 Y1+Y2+Y3 4
Y1+Y2+3Y3 6
2) для определения оптимального плана двойственной задачи воспользуемся соотношениями второй теоремы двойственности. Если какое-либо ограничение исходной задачи выполняется как строгое неравенство, то соответствующая двойственная оценка равна нулю.
().
15+25=40
15+3*25=90
Если какая-либо переменная исходной задачи входит в оптимальный план, то соответствующее ограничение двойственной задачи выполняется как строгое равенство
).
В нашей задаче x=15>0 и y=25>0, поэтому второе и третье ограничения двойственной задачи обращаются в уравнения, решая которые найдем Y1и Y2.
1 Y2+ 1Y3 = 4 Y2= 3 - средняя цена изделия
1 Y2+ 3Y3 = 6 Y3 = 1 - двойственная оценка капитальных вложений.
3 =4-1 = 3
3 =6-31 = 3
Целесообразно изготавливать товары на фрезерном станке так как затраты на его освоение и выпуск не превышают цену изделия.
Проверим выполнение первой теоремы двойственности.
g =70 Y1+40 Y2 +90 Y3 = 70 0+403+901 = 210
= 4x+6y=415+625= 210.
Полученные оптимальные планы говорят о том, что изготавливать товары на токарном станке на выгодно, так как затраты на производство единицы изделия больше цены изделия.
Размещено на Allbest.ru
...Подобные документы
Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Математическая формулировка экономико-математической задачи. Вербальная постановка и разработка задачи о составлении графика персонала. Решение задачи о составлении графика персонала с помощью программы Microsoft Excel. Выработка управленческого решения.
курсовая работа [1,2 M], добавлен 12.01.2018Транспортная задача линейного программирования, закрытая модель. Создание матрицы перевозок. Вычисление значения целевой функции. Ввод зависимостей из математической модели. Установление параметров задачи. Отчет по результатам транспортной задачи.
контрольная работа [202,1 K], добавлен 17.02.2010Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.
курсовая работа [30,5 K], добавлен 14.04.2004Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.
контрольная работа [80,8 K], добавлен 13.12.2010Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.
лекция [124,5 K], добавлен 15.06.2004Решение экономико-математических задач методами линейного программирования. Геометрическая интерпретация и решение данных задач в случае двух переменных. Порядок разработки экономико-математической модели оптимизации отраслевой структуры производства.
курсовая работа [116,4 K], добавлен 23.10.2011Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Роль экономико-математических методов в оптимизации экономических решений. Этапы построения математической модели и решение общей задачи симплекс-методом. Составление экономико-математической модели предприятия по производству хлебобулочных изделий.
курсовая работа [1,3 M], добавлен 09.07.2015Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.
презентация [1,1 M], добавлен 02.12.2014Построение математической модели, максимизирующей прибыль фирмы от реализации всех сделок в виде задачи линейного программирования. Сущность применения алгоритма венгерского метода. Составление матрицы эффективности, коэффициентов затрат и ресурсов.
контрольная работа [168,7 K], добавлен 08.10.2009Способы решения задач линейного программирования с вещественными числами симплекс-методом. Общие задачи, формы записи, максимизация и минимизация функции методом искусственного базиса. Пути поиска и исключения из базиса искусственных переменных.
контрольная работа [130,6 K], добавлен 09.02.2013Формулирование экономико-математической модели задачи в виде основной задачи линейного программирования. Построение многогранника решений, поиск оптимальной производственной программы путем перебора его вершин. Решение задачи с помощью симплекс-таблиц.
контрольная работа [187,0 K], добавлен 23.05.2010Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
курсовая работа [105,5 K], добавлен 02.10.2014
