Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Решение задачи распределения ресурсов в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции

Поиск решения

Задачи с небольшим числом неизвестных и ограничений могут быть решены симплексным методом вручную, задачи, содержащие большое количество неизвестных легко решаются в Microsoft Excel и OpenOffice.org Calc с помощью встроенной функции Поиск решения. При установке параметра Линейная модель решение здесь ищется так же с помощью симплекс-метода.

Замечание. Если флажок Линейная модель выключен, решение задач ведется методом Ньютона или градиентным методом.

Задача 4.Коммерческая организация имеет 9 видов ресурсов, запасы которых на планируемый период составляют соответственно: 1451,56; 1234,78; 1345,98; 1456,76; 1890,41; 1234,56; 1567,23; 1456,48 условных единиц. Имеющиеся ресурсы могут быть использованы для выпуска 4 видов продукции. В приведенной ниже таблице 9 даны технологические коэффициенты, т.е. расход каждого вида ресурса на производство единицы каждого вида продукции и прибыль от реализации единицы продукции каждого вида

Таблица 9

Ресурсы Технологические коэффициенты Запасы ресурса
1вид продукции 2вид продукции 3вид продукции 4вид продукции
5,23 6,09 6,56 4,51 1451,56
9,12 7,02 8,95 5,93 1234,78
8,14 7,49 6,51 7,12 1345,98
9,81 9,60 9,14 4,91 1456,76
2,43 4,28 8,25 8,15 1890,41
7,42 5,93 4,52 2,03 1234,56
7,23 9,13 8,62 5,82 1567,23
6,78 7,12 5,19 7,23 1456,48
6,35 5,14 7,24 4,45 1890,45
Прибыль от реализации 9,85 12,31 11,99 9,61  

 

Требуется составить такой план выпуска (т.е. определить какие виды продукции целесообразнее выпускать и в каком количестве) чтобы получить максимальную прибыль.

Составим математическую модель задачи на листе Excel (рис. 12). Обозначим через x1, x2, x3, x4 количество единиц соответствующей продукции; с1, с2, с3, с4 - прибыль от реализации единицы соответствующего вида продукции. Целевая функция задается с помощью встроенной функции СУММПРОИЗВ(В4:Е4;В6:Е6). В OpenOffice.org Calc используется функция SUMPRODUCT(В4:Е4;В6:Е6). Ограничения также зададим с помощью функции СУММПРОИЗВ в столбце F, для этого в ячейке F10 записываем формулу СУММПРОИЗВ ($В4$:$Е4$;В10:Е10) (SUMPRODUCT($В4$:$Е4$;В10:Е10)) при этом используем абсолютную адресацию для массива В4:Е4, чтобы можно было распространить формулы на все ячейки столбца «Расход ресурса».

После построения математической модели пользуемся встроенной функцией Поиск решения, чтобы получить оптимальное решение данной задачи.

 

 

Р и с. 12.

 

Задание

1. Решить задачи 1 и 2 из Л.Р.№1 с помощью симплекс-таблиц.

2. Найти оптимальное решение задачи 4 с помощью встроенной функции Поиск решения в редакторе Microsoft Excel.

Индивидуальное задание

1. Cформулировать свою задачу линейного программирования.

2. Составить математическую модель данной задачи, дав экономическую интерпретацию переменным, функции цели и системе ограничений.

3. Записать модель в стандартной и канонической формах.

4. Решить задачу симплекс-методом с помощью симплекс-таблиц.

5. Решить задачу с использованием встроенной функции Поиск решения в Microsoft Excel или OpenOffice.org Calc.Проанализировать полученный результат.

Контрольные вопросы

1. В чем заключается идея симплекс-метода?

2. В каком виде должна быть записана модель ЗЛП для решения симплекс-методом?

3. Как определить первоначальное допустимое базисное решение?

4. Из каких этапов состоит переход от одного базисного решения к другому?

5. Как определить разрешающий столбец в симплекс-преобразованиях?

6. Как определить разрешающую строку в симплекс-преобразованиях?

7. Что является критерием оптимальности решения ЗЛП в симплекс-методе?

8. Как определяется текущее значение целевой функции из таблицы?

9. По какому правилу вычисляются значения элементов новой симплекс-таблицы?

10. Какие параметры необходимо установить при решении задачи линейного программирования в Microsoft Excel, чтобы она была решена симплекс-методом?

11. Какая встроенная функция Microsoft Excel и OpenOffice.org Calc используется для записи математической модели ЗЛП с большим количеством неизвестных?

Лабораторная работа №3.

Двойственные задачи линейного программирования

Цель лабораторного занятия:

Приобретение навыков составления двойственных задач линейного программирования. Освоение приемов решения двойственных задач ЛП, в том числе в редакторах Microsoft Excel и OpenOffice.org Calc.

Задачи лабораторного занятия:

1. Построение математической модели двойственной ЗЛП.

2. Решение двойственной задачи в редакторах Microsoft Excel и OpenOffice.org Calc с помощью функции Поиск решения.

3. Получение решения двойственной задачи из решения исходной с использованием функций табличных редакторов Microsoft Excel и OpenOffice.org Calc МОБР() (MINVERSE()) и МУМНОЖ() (MMULT()).

4. Анализ полученных результатов.

5. Оформление отчета.

Содержание

1. Краткие теоретические сведения.

2. Алгоритм составления двойственной задачи.

3. Решение двойственной задачи.

4. Задание.

5. Контрольные вопросы.

Краткие теоретические сведения

Каждой задаче линейного программирования можно поставить в соответствие другую задачу тоже линейного программирования, которая получается из исходной задачи путем определенных преобразований и называется двойственной по отношению к данной исходной задаче.

Т.е. ЗЛП на максимум можно поставить в соответствие ЗЛП на минимум. Эти задачи называются симметричными или взаимно-двойственными.

Рассмотрим понятие двойственных задач на примере задачи 3 об использовании ресурсов (сырья) из Л.Р. №1:

В этой задаче прибыль от реализации 1м трикотажного полотна первого вида составляет 2 у.е., а трикотажного полотна второго вида 3 у.е.. Необходимо определить оптимальный план выпуска трикотажа первого и второго вида, чтобы обеспечить максимальную прибыль от их реализации.

Экономико-математическая модель задачи следующая: найти максимум целевой функции (функции прибыли):

при выполнении системы ограничений:

Предположим, что некоторая организация решила закупить ресурсы предприятия и необходимо установить оптимальные цены на эти ресурсы

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы (целевая функция Z) в количествах 80, 80, 260 и 410 у.е. по ценам были минимальны, т.е.

.

С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию.

На изготовление 1м трикотажного полотна I вида расходуется 0 у.е. первого ресурса (шерсти), 1 у.е. второго ресурса (хлопка), 1 у.е. третьего ресурса (вискозы) и 4 у.е. четветого ресурса (акрила). Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении 1м трикотажного полотна I вида по ценам , должны быть не менее цены 1м трикотажного полотна I вида 2 у.е., т.е.

Аналогично составим ограничение в виде неравенства по второму виду продукции (трикотажному полотну II вида):

.

Таким образом, мы получили двойственную задачу относительно исходной (таблица 10).

Таблица 10

Исходная задача Двойственная задача
  при ограничениях:   при ограничениях:
Матрица коэффициентов при переменных в системе ограничений Матрица коэффициентов при переменных в системе ограничений  

 

При этом цены ресурсов являются условными, в отличие от «внешних цен» на продукцию, известных, как правило, до начала производства.

Цены ресурсов так же называются «внутренними» (или оценками ресурсов), т.к. они задаются не извне, а определяются непосредственно в результате решения задачи.

Исходную задачу можно рассматривать как двойственную по отношению к своей двойственной задаче, т.е. обе задачи являются взаимно двойственными.

Взаимно двойственные задачи обладают следующими свойствами:

1. В одной задаче определяется максимум целевой функции, в другой – минимум.

2. Коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений в другой.

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида , а в задаче минимизации – все неравенства вида .

4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу.

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

Последнее изменение этой страницы: 2016-07-23

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...