Решение векторных задач линейного программирования различными методами с использованием MS Excel
Решение задач линейного программирования с помощью MS Excel методами главной компоненты, свертывания критериев, последовательных уступок, сведения к лямбда задаче. Выбор метода расчета прибыли, оптовой цены, себестоимости и уровня загрузки оборудования.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | лабораторная работа |
Язык | русский |
Дата добавления | 19.05.2016 |
Размер файла | 2,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Государственное бюджетное образовательное учреждение высшего профессионального образования
Уфимский государственный нефтяной технический университет
Лабораторная работа
Тема: «Решение векторных задач линейного программирования различными методами с использованием MS Excel»
Уфа 2016
Цель работы: Решения векторных задач линейного программирования (ВЗЛП) с использованием MS Excel различными методами. Сравнение и анализ результатов.
Экономическая постановка задачи: Предприятие выпускает пять видов продукции И1, И2, ИЗ, И4, И5. Для этого используется три вида ресурсов и приведены данные о расходах на производство единицы продукции и запасах. Все изделия обрабатываются на станках четырех типов, по которым предоставлены данные о норме времени на обработку одного изделия и фонде времени работы станков. Также имеются данные об оптовой цене и себестоимости единицы продукции.
Объем каждого вида продукции должен быть не менее 100 и не более 500 единиц. Мерой эффективности производственной программы являются следующие показатели:
1. Прибыль предприятия - f1;
2. Валовый объем выпуска продукции в стоимостном выражении - f2;
3. Себестоимость продукции - f3;
4. Уровень загрузки оборудования - f4.
Требуется:
1. Решить задачу методом главной компоненты, выбрав в качестве главной компоненты прибыль, а на остальные наложить разумные по смыслу задачи ограничения
2. Решить задачу методом свертывания критериев, выбрав вектор весовых коэффициентов равным (0,4; 0,3; 0,2; 0,1).
3. Решить задачу методом последовательных уступок, если уступку по каждому критерию полагать равной 10% от его оптимального значения.
4. Решить задачу методом сведения к лямбда задаче.
5. Сравнить итоговые результаты, полученные по 4 методам и принять решения о выборе приемлемого (оптимального) варианта.
линейный еxcel компонента свертывание
Исходные данные задачи
Ресурс |
И1 |
И2 |
И3 |
И4 |
И5 |
Запасы |
|
В1 |
4 |
1 |
4 |
3 |
1 |
2100 |
|
В2 |
3 |
3 |
2 |
4 |
3 |
3100 |
|
В3 |
4 |
3 |
4 |
5 |
3 |
3500 |
Вид станков |
И1 |
И2 |
И3 |
И4 |
И5 |
Фонд времени (ст./час) |
|
Токарные |
1 |
1 |
3 |
5 |
3 |
2400 |
|
Фрезерные |
4 |
6 |
2 |
1 |
3 |
3500 |
|
Сверлильные |
2 |
5 |
2 |
4 |
5 |
4000 |
|
Шлифовальные |
2 |
3 |
2 |
4 |
1 |
2100 |
И1 |
И2 |
И3 |
И4 |
И5 |
||
Оптовая цена (ден.ед) |
11 |
13 |
12 |
15 |
12 |
|
Себестоимость (ден.ед) |
4 |
5 |
6 |
7 |
8 |
Ход работы:
Целевая функция и ограничения данной задачи имеют вид
L(x)=(11x1+13x2+12x3+15x4+12x5)-(4x1+5x2+6x3+7x4+8x5) max
4x1+1x2+4x3+3x4+1x5 2100
3x1+3x2+2x3+4x4+3x5 3100
4x1+3x2+4x3+5x4+3x5 3500
1x1+1x2+3x3+5x4+3x5 2400
4x1+6x2+2x3+1x4+3x5 3500
2x1+5x2+2x3+4x4+5x5 4000
2x1+3x2+2x3+4x4+1x5 2100
100 Xi 500; Xi - целые
В Microsoft Excel создаем таблицу первоначальных данных: о ресурсах на производство, о станках, об оптовой цене и о себестоимости.
Создается таблица с переменными.
Создаем ограничения для использования ресурсов (левая часть ограничения получается произведением соответствующей строки по каждому виду ресурса на строку переменных) и времени работы станков (левая часть ограничения получается произведением соответствующей строки для каждого вида станка на строку переменных ).
Также получаем значения «всего» для оптовой цены, себестоимости и загрузки оборудования (значение функции для оптовой цены и себестоимости получаем произведением соответствующей строки на строку переменных; значение функции для загрузки оборудования получаем путем суммирования левых частей ограничения времени работы станков).
И определяем целевую функцию. Ее значение рассчитывается по формуле:
=G15-G16(оптовая цена-себестоимость) в ячейке H20 и c направлением max.
Формулы экранной формы задачи
Объект математической модели |
Выражение в Excel |
|
Переменные задачи |
В20:F20 |
|
Формула целевой функции |
=G15-G16 |
|
Ограничения по ресурсам |
=СУММПРОИЗВ(B3:F3;B20:F20) =СУММПРОИЗВ(B4:F4;B20:F20) =СУММПРОИЗВ(B5:F5;B20:F20) |
|
Ограничения по станкам |
=СУММПРОИЗВ(B8:F8;B20:F20) =СУММПРОИЗВ(B9:F9;B20:F20) =СУММПРОИЗВ(B10:F10;B20:F20) =СУММПРОИЗВ(B11:F11;B20:F20) |
|
Функция оптовой цены |
=СУММПРОИЗВ(B15:F15;B20:F20) |
|
Функция себестоимости |
=СУММПРОИЗВ(B16:F16;B20:F20) |
|
Функция загрузки оборудования |
=СУММ(G8:G11) |
Воспользуемся сервисом «Поиск решений» для получения первоначальной таблицы промежуточных данных (рис.1,2).
Рис.1
Рис.2
По аналогии ограничения вводятся для целевой ячейки оптовой цены (G15) - max, уровня загрузки оборудования (G12) - max; для себестоимости (G16) - min.
В результате получаем таблицу промежуточных данных, которые в дальнейшем будут использоваться для решения задачи различными методами (рис.3):
Рис.3
В таблице ниже представлены максимальные значения по прибыли, оптовой цене, уровню загрузки и минимальные значения по себестоимости:
Решим данную задачу 4 различными методами:
1) Метод главной компоненты
В качестве главной компоненты - функции цели мы выбираем прибыль. На остальные показатели - оптимальную цену, себестоимость и загрузку оборудования накладываем ограничения. Оптовая цену и загрузку оборудования уменьшаем на 20%, себестоимость увеличиваем на 100%. Таким образом, формулы для расчета показателей следующие:
Оптовая цена (умен. на 20%) |
=C24*0,8 |
|
Загрузка оборудования (умен. на 20%) |
=E26*0,8 |
|
Себестоимость (увел. на 100%) |
=D25*2 |
Ячейки С24, D25, E26 - максимальные значения для оптовой цены и загрузки оборудования, минимальное значение для себестоимости (значения показателей из таблицы промежуточных данных)
Получаем таблицу (рис.4):
Рис.4
Воспользуемся сервисом «Поиск решений» для решения задачи. Накладываем ограничения для показателей f2, f3, f4, в качестве целевой ячейки выбираем прибыль (max) (рис.5,6).
Рис.5
Рис.6
В результате получаем решение задачи методом главной компоненты (рис.7):
Рис.7
2) Метод свертывания критериев
Выбираем вектор весовых коэффициентов равных (0,4; 0,3; 0,2; 0,1).
Для решения данной задачи вводим новую целевую функцию используя вектор весовых коэффициентов (0,4; 0,3; 0,2; 0,1).
Формула ЦФ следующая:
=0,4*H20+0,3*G15-0,2*G16+0,1*G12
Воспользуемся сервисом «Поиск решений» для решения задачи (все ограничения, используемые при решении задачи методом главной компоненты удаляются, а в качестве целевой ячейки берется новая полученная ЦФ) (рис.8,9).
Рис. 8
Рис. 9
В результате получаем решение задачи методом свертывания критериев (рис.10):
Рис. 10
3) Метод последовательных уступок
Уступку по каждому критерию следует полагать равной 10% от его оптимального значения.
Данный метод решается в несколько последовательных шагов с помощью сервиса «Поиск решения».
- Для начала берем максимальное значение прибыли из таблицы промежуточных значений (=6124). По каждому критерию делается уступка в 10%, соответственно уступка по прибыли будет рассчитываться по формуле:
=0,9*C50 (где С50 - ячейка со значением прибыли).
Используем сервис «Поиск решения», добавляем ограничения для прибыли и устанавливаем целевую ячейку - оптовая цена - max (рис.11, 12).
Рис. 11
Рис. 12
-
- Затем рассчитываем уступку в 10% от полученного значения оптовой цены по формуле:
=0,9*C51 (где С51 - ячейка со значением оптовой цены).
Используем сервис «Поиск решения», добавляем ограничение для оптовой цены и устанавливаем целевую ячейку - себестоимость - min (рис.13,14).
Рис. 13 Рис. 14
- Далее шаге рассчитываем уступку в 10% для полученного значения себестоимости по формуле:
=1,1*C52 (где С52 - ячейка со значением себестоимости).
Используем сервис «Поиск решения», добавляем ограничение для себестоимости и в качестве целевой ячейки выбираем уровень загрузки оборудования - max (рис.15,16).
Рис.15 Рис.16
В результате получаем решение задачи методом последовательных уступок (рис.17):
Рис. 17
4) Метод сведения к лямбда задаче
- Для решения задачи сначала необходимо определить обратные значения для показателей, т.е. с помощью сервиса «Поиск решений» определяем минимальное значение для прибыли, оптовой цены, уровня загрузки оборудования и максимальное значение для себестоимости.
Получаем:
Прибыль |
Оптовая цена |
Себестоимость |
Уровень загрузки оборудования |
|
3300 |
6300 |
6300 |
5900 |
Затем проводим нормализацию критериев:
Критерии |
Формулы |
|
Прибыль |
=(H20-B58)/(B23-B58) |
|
Оптовая цена |
=(G15-C58)/(C24-C58) |
|
Себестоимость |
=(D58-G16)/(D58-D25) |
|
Уровень загрузки оборудования |
=(G12-E58)/(E26-E58) |
Получаем:
Нормализация критериев |
||||
Прибыль |
Оптовая цена |
Себестоимость |
Уровень загрузки |
|
0,956 |
0,996 |
0 |
0,984 |
Строим л задачу:
Max L |
||
0 |
L |
|
-0.956 |
L-L1<=0 |
|
-0.996 |
L-L2<=0 |
|
0 |
L-L3<=0 |
|
-0.984 |
L-L4<=0 |
Используем сервис «Поиск решения». Вводим ограничения для ячеек L-Li <=0 и устанавливаем целевую ячейку L (F60) (рис.18,19).
Рис.18
Рис.19
В результате получаем решение задачи методом сведения к лямбда задаче:
Рис. 20
Сравним итоговые результаты, полученные по 4 методам и выбираем оптимальный вариант (рис.21).
Рис. 21
Сравнив полученные результаты по каждому показателю по 4 методам, можно сделать вывод о том, что оптимальным из всех 4 методов является метод свертывания критериев.
Вывод
В данной лабораторной работе мы получили навыки решения задач линейного программирования с помощью MS Excel 4-мя различными методами, а именно методом главной компоненты, методом свертывания критериев, методом последовательных уступок и решение лямбда методом. На основе полученного решения, мы сделали вывод, что наиболее оптимальным из всех предложенных методов является метод свертывания критериев, так как по таким параметрам как прибыль, оптовая цена, себестоимость и уровень загрузки оборудования он превосходит остальные (имеет максимальное значение из всех 4 методов. Таким образом, прибыль по нему составила 6122, оптовая цена 12316, себестоимость 6194 и уровень загрузки оборудования 11962.
Размещено на Allbest.ru
...Подобные документы
Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.
курсовая работа [1,1 M], добавлен 27.08.2012Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010История развития и функции линейного программирования. Исследование условий типовых задач и возможностей табличного процессора. Решение задач о рационе питания, плане производства, раскрое материалов и рациональной перевозке груза в среде MS Excel.
курсовая работа [3,3 M], добавлен 28.04.2014Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Принципы решения задач линейного программирования в среде электронных таблиц Excel, в среде пакета Mathcad. Порядок решения задачи о назначении в среде электронных таблиц Excel. Анализ экономических данных с помощью диаграмм Парето, оценка результатов.
лабораторная работа [2,0 M], добавлен 26.10.2013Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Решение задачи расчета структуры и объема товарооборота методом линейного программирования. Формулы ограничений, транспортная задача оптимизации доставки товаров. Решение задачи о назначениях на основе матрицы стоимостей в электронной таблице Excel.
контрольная работа [1023,6 K], добавлен 27.05.2013Решение задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях. Компьютерная реализация выбранных задач нелинейного программирования в среде пакетов Excel и Matlab.
дипломная работа [2,9 M], добавлен 25.01.2013Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов.
курсовая работа [514,8 K], добавлен 04.02.2011Планирование прибыли при производстве двух видов топлива. Составление оптимального плана выпуска продукции для получения максимальной прибыли от ее реализации. Определение опорного плана перевозок грузов методом минимальной стоимости и с помощью Excel.
контрольная работа [32,5 K], добавлен 12.11.2014Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Определение с помощью симплекс-метода плана выпуска продукции для получения максимальной прибыли, чтобы сырьё II вида было израсходовано полностью. Решение задач линейного программирования средствами табличного процессора Excel, составление алгоритма.
курсовая работа [53,2 K], добавлен 30.09.2013Определение количества и вида тракторных и автомобильных глушителей, которые следует изготовить предприятию, чтобы прибыль была максимальной. Решение задачи линейного программирования графическим и симплекс-методом, с помощью табличного редактора Excel.
курсовая работа [1,3 M], добавлен 09.04.2013