Изучив алгоритмы "ручного" решения задач линейного программирования, полезно познакомиться и со способом упростить этот процесс. Ясно, что чем сложнее задача, чем больше в ней переменных и условий, тем утомительнее и дольше ее решать. В таких случаях удобно использовать специальные математические пакеты, или доступную многим программу MS Excel.

Решить задачи линейного программирования в Excel достаточно просто: 1) внести исходные данные задачи и ограничения, 2) запустить надстройку Поиск решения, 3) установить нужные параметры решения и запустить выполнение. Программа подберет оптимальное решение, выдаст отчеты для анализа решения задачи.

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


Линейное программирование: примеры решений в Excel

Задача 1. Построить математическую модель задачи и решить её средствами Excel. Записать сопряжённую задачу. Провести анализ и сделать выводы по полученным результатам.
Для производства столов и шкафов мебельная фабрика использует различные ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в таблице.
Определить, сколько столов и шкафов фабрике следует выпускать, чтобы прибыль от реализации была максимальной.

Задача 2. Цех производит 8 различных видов деталей для двигателей A, B, C1, C2, C3, D, E6, F имея в своем распоряжении перечисленный ниже парк из 7 видов универсальных станков: 2 шт. -ADF, 3 шт. -SHG, 3 шт. -BSD, 1 шт. -AVP, 1 шт. -BFG, 3 шт. -ABM, 2 шт. -RL.
Время, требуемое для обработки единицы каждого продукта на каждом станке, вклад в прибыль от производства единицы каждого продукта и рыночный спрос на каждый продукт за месяц даны в таблице.
Цех работает 12 часов в день. Каждый месяц содержит 26 рабочих дней. Для упрощения задачи считаем, что возможен произвольный порядок обработки деталей на различных станках.
Составьте оптимальный план производства.
Определите, производство каких продуктов лимитировано рынком, и каких – техническими возможностями цеха. Какие машинные ресурсы должны быть увеличены в первую очередь, чтобы добиться максимального увеличения прибыли (при заданных потребностях рынка)?
Есть ли продукт, который невыгодно производить? Почему? Что нужно изменить, чтобы все продукты стало выгодно производить?



Задача 3. Необходимо составить самый дешевый рацион питания цыплят, содержащий необходимое количество определенных питательных веществ тиамина Т и ниацина Н. Пищевая ценность рациона (в калориях) должна быть не менее заданной. Смесь для цыплят изготавливается из двух продуктов - К и С. Известно содержание тиамина и ниацина в этих продуктах, а также питательная ценность К и С (в калориях). Сколько К и С надо взять для одной порции куриного корма, чтобы цыплята получили необходимую им дозу веществ Н и Т и калорий (или больше), а стоимость порции была минимальна? Исходные данные для расчетов приведены в таблице.

Задача 4. Фирма "Компьютер-сервис" поставляет компьютеры под ключ четырех базовых комплектаций: «домашний», «игровой», «офисный» и «экстрим». Известны средние затраты времени на сборку, проверку и подключение компьютеров. Каждый компьютер приносит определенный уровень прибыли, но спрос ограничен. Кроме того, в плановом периоде ограничен ресурс человеко-часов, отведенных на выполнение каждой производственной операции. Определить, сколько компьютеров каждого типа необходимо произвести в плановом периоде, имея целью максимизировать прибыль.

Задача 5. На лесопилку поступают доски длиной 10 м. По контракту лесопилка должна поставить клиенту не менее 100 досок длиной 5 м, не менее 200 досок длиной 4 м и не менее 300 досок длиной 3 м. Как работникам лесопилки выполнить условия контракта, разрезав наименьшее количество досок?

Задача 6. Компания "Евростройтур" организует экскурсионные автобусные туры по странам Европы. Компания получила 4 новых автобуса и предполагает направить их на маршруты во Францию, Италию, Чехию и Испанию. Каждый автобус обслуживают 2 водителя. Компанией приглашены 8 водителей, в различной степени знакомых с дорогами европейских стран (в % от экскурсионного маршрута).
Необходимо распределить водителей так, чтобы общий показатель освоения маршрутов был максимальным.

Задача 7. Решить задачу методом ветвей и границ, решая отдельные задачи линейного нецелочисленного программирования с помощью функции "Поиск решения" в Microsoft Excel (в случае, если первая же задача ЛП выдает целочисленное решение, не позволяя ветвить задачу, немного изменить начальные условия).
Состав еды рядовых регламентируется верховной ставкой главнокомандующего, которая устанавливает нижние нормы питания в сутки по основным компонентам: 1500 килокалорий, 100 г белков, 280 г углеводов, 90 г жиров, 1 кг воды. На складах есть 4 вида продуктов, которые выдают защитникам Родины сухим пайком: лимонад, тушенка в маленьких банках, унифицированные наборы горбушек и пирожки с ежевикой. Стоимость этих четырех продуктов соответственно 12 руб., 34 руб., 3 руб. и 20 руб. Какова минимальная сумма, которую должен затратить прапорщик на питание одного солдата?

Задача 8. Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа.
На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, a22 кг сырья второго типа, a32 кг сырья третьего типа.
Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно.
Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 - c2 тыс.руб.
Требуется:
1) построить экономико – математическую модель задачи;
2) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.
3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования.
4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL.

Использование Microsoft Excel для решения задач линейного программирования .

В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel , нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel » внизу окна:


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

Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:

1. Ввести условие задачи:

a) создать экранную форму для ввода условия задачи :

· переменных,

· целевой функции (ЦФ),

· ограничений,

· граничных условий;

b) ввести исходные данные в экранную форму :

· коэффициенты ЦФ,

· коэффициенты при переменных в ограничениях,

· правые части ограничений;

c) ввести зависимости из математической модели в экранную форму :

· формулу для расчета ЦФ,

· формулы для расчета значений левых частей ограничений;

d) задать ЦФ (в окне "Поиск решения" ):

· целевую ячейку,

· направление оптимизации ЦФ;

e) ввести ограничения и граничные условия (в окне "Поиск решения" ):

· ячейки со значениями переменных,

· граничные условия для допустимых значений переменных,

· соотношения между правыми и левыми частями ограничений.

2. Решить задачу:

a) установить параметры решения задачи (в окне "Поиск решения" );

b) запустить задачу на решение (в окне "Поиск решения" ) ;

c) выбрать формат вывода решения (в окне "Результаты поиска решения" ).

Рассмотрим подробно использование MS Excel на примере решения следующей задачи.

Задача.

Фабрика "GRM pic" выпускает два вида каш для завтрака - "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основ-ном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.

Управляющему производством Джою Дисону необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.


Цех
Необходимый фонд рабочего времени
чел.-ч/т
Общий фонд рабочего времени
чел.-ч. в месяц

"Crunchy"
"Chewy"

А. Производство


10
4
1000

В. Добавка приправ


3
2
360

С. Упаковка


2
5
600

Доход от производства 1 т "Crunchy" составляет 150 ф. ст., а от производства "Chewy" - 75 ф, ст. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.

Требуется:

а) Сформулировать модель линейного программирования, максимизи-рующую общий доход фабрики за месяц.

б) Решить ее c помощью MS Excel.

Формальная постановка данной задачи имеет вид:

(1)
Ввод исходных данных
Создание экранной формы и ввод исходных данных

Экранная форма для решения в MS Excel представлена на рисунке 1.


Рисунок 1.

В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (), C4 (), коэффициентам ЦФ соответствуют ячейки B6 (150), C6 (75), правым частям ограничений соответствуют ячейки D 18 (1000), D 19 (360), D 20 (600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму

Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ , которая вычисляет сумму попарных произведений двух или более массивов.

Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций", который можно вызвать из меню "Вставка" или при нажатии кнопки "

Рисунок 2

Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:

· курсор в поле D 6;

· нажав кнопку "

· в окне "Функция" выберитефункцию СУММПРОИЗВ (рис. 3);


Рисунок 3

· в появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение B $4: C $4 , а в строку "Массив 2" - выражение B 6: C 6 (рис. 4);

Рисунок 4

Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B 3, C 3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B 13, C 13 - 1-е ограничение; B 14, С14 - 2-е ограничение и B 15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.

Таблица 1.
Формулы, описывающие ограничения модели (1)


Левая часть ограничения
Формула Excel


=СУММПРОИЗВ(B 4: C 4; B 13: C 13))


=СУММПРОИЗВ(B 4: C 4; B 14: C 14))


=СУММПРОИЗВ(B 4: C 4; B 15: C 15)

Задание ЦФ

Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):

· поставьте курсор в поле "Установить целевую ячейку" ;

· введите адрес целевой ячейки $ D $6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;

· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".


Рисунок 5
Ввод ограничений и граничных условий
Задание ячеек переменных

В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $ B $4:$С$4 . Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных

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

· Нажмите кнопку "Добавить" , после чего появится окно "Добавление ограничения" (рис.6).

· В поле "Ссылка на ячейку" введите адреса ячеек переменных $ B $4:$С$4 . Это можно сделать как с клавиатуры, так и путем выделения мышью всех ячеек переменных непосредственно в экранной форме.

· В поле знака откройте список предлагаемых знаков и выберите .

· В поле "Ограничение" введите 0.

Рис.6 - Добавление условия неотрицательности переменных задачи (1)
Задание знаков ограничений , , =

· Нажмите кнопку "Добавить" в окне "Добавление ограничения" .

· В поле "Ссылка на ячейку" введите адрес ячейки левой части конкретного ограничения, например $ B $18 . Это можно сделать как с клавиатуры, так и путем выделения мышью нужной ячейки непосредственно в экранной форме.

· В соответствии с условием задачи (1) выбрать в поле знака необходимый знак, например, .

· В поле "Ограничение" введите адрес ячейки правой части рассматриваемого ограничения, например $ D $18 .

· Аналогично введите ограничения: $ B $19<=$ D $19 , $ B $20<=$ D $20 .

· Подтвердите ввод всех перечисленных выше условий нажатием кнопки OK .

Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.

Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).
Решение задачи
Установка параметров решения задачи

Задача запускается на решение в окне "Поиск решения". Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).

Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП

Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).

Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.

Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.

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

Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.

Подтвердите установленные параметры нажатием кнопки " OK " .
Запуск задачи на решение

Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить".

После запуска на решение задачи ЛП на экране появляется окно "Результаты поиска решения" с сообщением об успешном решении задачи, представленном на рис. 8.


Рис. 8 -. Сообщение об успешном решении задачи

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

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации увеличивайте погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.

В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы" . Они необходимы при анализе полученного решения на чувствительность. Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме просто нажмите кнопку " OK ". После этого в экранной форме появляется оптимальное решение задачи (рис. 9).


Рис.9 - Экранная форма задачи (1) после получения решения

Цель: научиться решать задачи линейного программирования в Excel с помощью надстройки «Поиск решения».

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

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

Постановка задачи линейного программирования (ЗЛП).

Имеется множество переменных X= (x 1 , х 2 ,..., х n). Целевая функция линейно зависит от управляемых параметров:

Имеются ограничения, которые представляют собой линейные формы

где (2)

Требуется определить максимум (минимум) линейной функции

при условии, что точка (х 1 , х 2 ,..., х n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

(4)

Любое множество значений (х 1 *, х 2 *,..., х n *), которое удовлетворяет системе неравенств (4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство

c 1 х 1 o + c 2 х 2 o +..+ c n х n o ≥ c 1 х 1 + c 2 х 2 +..+ c n х n

для всего множества значений x 1 , х 2 ,..., х n , то значение х 1 o ..х n o является оптимальным решением задачи линейного программирования.

Пример построения математической модели и решения ЗЛП.

Задача. Требуется определить, в каком количестве надо выпускать продукцию четырех типов A, B, C иD, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице1. Там же приведено наличие располагаемого ресурса.

Таблица1.

Ресурс

A

B

C

D

знак

наличие

трудовые

Составим математическую модель, для чего введем следующие обозначения:

x i - количество выпускаемой продукции i-го типа, i = 1,2,3,4

b j – количество располагаемого ресурса j-го вида, j = 1,2,3

a ji – норма расхода j-го ресурса для выпуска i-ой продукции

c i – прибыль от реализации единицы продукции i-го типа.

Как видно из таблицы 1, для выпуска единицы продукции A требуется 6 единиц сырья, значит, для выпуска всей продукции A требуется 6x 1 единиц сырья, где x 1 - количество выпускаемой продукции A . С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:

6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110

В этом ограничении левая часть равна величине требуемого ресурса, а правая часть показывает количество имеющегося ресурса.

Аналогично можно составить ограничения для других видов ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:

x 1 + x 2 + x 3 + x 4 ≤ 16

6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110

4x 1 + 6x 2 + 10x 3 + 13x 4 ≤ 100

x i ≥ 0, i=1,2,3,4

1. Для ввода условий задачи создадим форму в Excel (рис.1). В ячейках B3:E3 будут отображаться вычисленные значения x i .


рис.1. Форма для ввода условий задачи

2. Введем коэффициенты целевой функции и ограничений в форму. Из математической модели введем зависимости. Введенные данные отображены на рис.2.


рис.2. Исходные данные задачи

В ячейке F6 записана формула целевой функции, в F9-F11- левые части ограничений из математической модели. На рис. 3 отображен режим представления формул. Перейти к данному режиму можно с помощью последовательности действий: нажмите кнопку Microsoft Office , щелкните Параметры Excel, откройте вкладку Дополнительно и установите флажок Показывать формулы, а не их значения.


рис.3. Режим представления формул.

3. Загрузим надстройку поиск решения Данные │Анализ │Поиск решения .

4. В поле Установить целевую ячейку введем ссылку на целевую ячейку, для чего установим курсор в поле и щелкнем левой кнопкой мыши по ячейке F6.

5. Выберем направление поиска, установив флажок равной максимальному значению.

6. Установим курсор в поле Изменяя ячейки и введем с помощью мыши имена изменяемых ячеек B3:E3. В этих ячейках в результате поиска решения будет выведено решение – значения переменных x i ., при которых целевая функция имеет максимальное значение при заданных ограничениях.

7. Введем ограничения на искомые переменные: x i ≥ 0 (нижняя граница по умолчанию равна 0, количество выпускаемой продукции не может быть отрицательным). Так же введем ограничения на ресурсы (н е может быть использовано больше ресурсов, чем их запасы). Щелкнем по кнопке Добавить , в появившемся окне Добавление ограничения в левом поле с помощью мыши введем ссылку на ячейку B3, из раскрывающегося списка выберем знак ≥, в правом поле щелкнем мышью по ячейкеB4 (рис.4). Аналогично введем остальные ограничения.


Рис.4. Окно добавления ограничений.

На рисунке 5 показано заполненное окно Поиск решения.


Рис.5 Заполненное окно Поиск решения

8. Далее нажимаем на кнопку Выполнить. Появляется диалоговое окно Результаты поиска решения (рис.6). Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраняем найденное решение. В этом окне также можно получить три вида отчетов: по результатам, устойчивости и пределам, отчеты формируются в новых рабочих листах.


рис.6. Окно Результаты поиска решения

Результаты оптимального решения задачи приведены в таблице (рис.7).


рис.7. Результаты оптимального решения

Таким образом, получилось оптимальное решение (10;0;6;0), т.е. целесообразно выпускать 10 единиц продукции А и 6 единиц продукции С. Максимальная прибыль равна 1320 денежным единицам, при этом используются все трудовые и финансовые ресурсы, 84 единиц сырья, в запасе остается 26 единиц сырья.

Задания для лабораторной работы.

Составить математическую модель и решить полученную задачу линейного программирования в Excel с помощью надстройки Поиск решения.

Для перевозки грузов используются машины типов А и Б. Грузоподъемность машин обоих типов одинаковая и равна h т. За одну ходку машина А расходует а 11 кг смазочных материалов и а 12 л горючего, машина Б - а 21 кг смазочных материалов иа 22 л горючего. На базе имеется d 1 кг смазочных материалов и d 2 л горючего. Прибыль от перевозки одной машины А составляет с 1 руб., машины Б - с 2 руб. Необходимо перевезти H т груза (исходные данные приведены в нижеследующей таблице).

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

№ варианта

Инструкция по выполнению лабораторной работы.

  1. Изучить теоретический материал.
  2. Выполнить приведенный пример.
  3. Выбрать свой вариант по последней цифре.
  4. Составить математическую модель задачи.
  5. Найти оптимальное решение с помощью Поиска решения.
  6. Сделать выводы по полученным решениям, сформировать отчеты по результатам решения, устойчивости и пределам.
  7. Создать отчет по лабораторной работе.
  1. Титульный лист.
  2. Словесная постановка задачи.
  3. Математическая формулировка задачи.
  4. Заполненное окно Поиск решения
  5. Результаты поиска решения (таблица).
  6. Выводы по полученным решениям.

Список источников

  1. Гельман В.Я. Решение математических задач средствами Excel: Практикум. – СПб.:Питер, 2003
  2. Курицкий Б.Я. Поиск оптимальных решений средствами Excel. – СПб.: BHV-Санкт-Петербург, 1997
  3. Пазюк К.Т. Математические методы и модели в экономике. – Хабаровск: Издательство ХГТУ, 2002
  4. Джон Уокенбах. MS OfficeExcel 2007 - Библия пользователя, Издатель: Вильямс, 2008

Лабораторная работа "Использование средства Поиск решения"

Задание:

Решить в Excel все приведенные ниже задачи (каждую на отдельном листе) и сохранить решения в файле LAB4.xls на своем пользовательском диске.

Задача 1 1

Решение задачи линейного программирования с помощью EXCEL. 2

Задача 2 4

Задача планирования производства красок 4

Задача 3 5

Решение транспортной задачи с помощью средства Поиск решения 5

Задача 1

Задача распределения ресурсов.

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

Например:

Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведена ниже.Составим математическую модель, для чего введем следущие обозначения:

x j - количество выпускаемой продукции j-го типа, j=1,4 ;

b i - количество располагаемого ресурса i-го вида, i=1,3 ;

a ij - норма расхода i-го ресурса для выпуска единицы продукции j-го типа;

c j - прибыль, получаемая от реализации единицы продукции j-го типа.

Теперь приступим к составлению модели.

Для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6 х 1 единиц сырья, где х 1 - количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:

6х 1 +5х 2 +4х 3

В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса. Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:

F=60x 1 +70x 2 +120x 3 +130x 4 --> max

x 1 +x 2 +x 3 +x 4

6x 1 +5x 2 +4x 3 +3x 4

4x 1 +6x 2 +10x 3 +13x 4

x j >=0; j=1,4

Решение задачи линейного программирования с помощью EXCEL.

1
. Сделать активной ячейку F6.

2. Мастер функций Математические СУММПРОИЗВ на жмите кнопку Далее. На экране диалоговое окно


3. Введите зависимости для левых частей ограничений.

Работа в диалоговом окне Поиск решения.

1

. Сервис, Поиск решения...

2 . Курсор в поле Установить целевую ячейку и введите адрес F6.

3 . Введите направление целевой функции: Максимальному значению .

4 . Курсор в поле Изменяя ячейки и введите адреса B3:E3

5. Нажмите кнопку Добавить... и в ведите граничные условия на переменные

6. После ввода ограничений, нажмите кнопку Выполнить . В результате вычислений в ячейках В3:Е3, будут отражены найденные числовые значения х i , а в ячейке F6 – значение целевой функции.

Т.О, видно, что в оптимальном решении Прод1=В3=10, Прод2=С3=0, Прод3=D3=6, Прод4=Е3=0.

При этом максимальная прибыль будет составлять F6=1320 , количество использованных ресурсов равно трудовых=F9=16, сырья=F10=84, финансов=F11=100.




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

Задача 2

Задача планирования производства красок

Для производства красок для наружных и внутренних работ используют два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.

Суточный спрос на краску для внутренних работ никогда не превышает спроса на краску для наружных работ более чем на 1т.

Спрос на краску для внутренних работ не превышает 2т. в сутки.

Оптовые цены одной тонны красок равны: 3000 руб. для краски для наружных работ и 2000 руб. для краски для внутренних работ .

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

Расходы продуктов А и В на 1т. приведены в таблице:

исходный продукт

расход исходных продуктов на тонну краски

максимально возможный запас

для внутренних работ

для наружных работ

х 1 - суточный объем производства краски для внутренних работ

х 2 - суточный объем производства краски для наружных работ

f -суммарная суточная прибыль от производства обоих видов красок (целевая функция)

f = 3000х 1 +2000х 2

Определить при каких допустимых значениях х 1 и х 2 значение f - максимальное

Ограничения:

Решение задачи в Excel

Переменные

Целевая функция:

3000*А3+2000*В3

Ограничения

Выполните: Cервис, Поиск решения

Целевая ячейка С4

Установить: М аксимальному значению

Изменяемые ячейки: А3:В3

Ограничения:

После ввода данных нажмите кнопку Выполнить

Полученное решение:

Переменные

Целевая функция:

Ограничения:

Вывод: оптимальным является производство 3,3 т. краски для наружных работ и 1,3 т. краски для внутренних работ в сутки. Этот объем принесет прибыль 12,7 тыс. руб.

Задача 3

Решение транспортной задачи с помощью средства Поиск решения

Фирма имеет четыре фабрики: А, В, С, D и пять центров распределения ее товаров: №1, №2, №3, №4, №5.

Производственные возможности фабрик соответственно составляют:

А – 200, В – 150, С – 225, D – 175 единиц продукции ежедневно.

Потребности центров распределения соответственно составляют:

№1 – 100, №2 – 200, №3 – 50, №4 – 250, №5 – 150 единиц продукции ежедневно.

Хранение на фабрике единицы продукции, не поставленной в центр распределения, составляет $0,75 в день.

Штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день.

Стоимость перевозки единицы продукции с фабрик в пункты распределения представлена в таблице:

Спланировать перевозки так, чтобы минимизировать суммарные транспортные расходы.

Модель рассматриваемой задачи сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), значит не нужно учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель следует ввести:

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

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

x ij – объем перевозок с i-й фабрики в j-й центр распределения.

c ij – стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения.

а i – объем производства на i-й фабрике.

в j – спрос в j-м центре распределения.

Т

ребуется минимизировать суммарные транспортные расходы, т.е.

Ограничения:

x



ij 0 , i , j

Механизм решения задачи в Excel с использованием средства Поиск решения

    В ячейки А1:Е4 введите стоимости перевозок.

    А6:Е9 – отведите под значения неизвестных (объемы перевозок).

    В ячейки G6:G9 введите объемы производства на фабриках.

    В А11:Е11 – потребность в продукции в пунктах распределения.

    В ячейку F10 – введите целевую функцию

    В А10:Е10 –введите формулы, определяющие объем продукции, ввозимой в центры распределения

    В F6: F9 – формулы, вычисляющие объем продукции, вывозимой с фабрик.

СУММ(A6:E6)

СУММ(A7:E7)

СУММ(A8:E8)

СУММ(A9:E9)

СУММ(A6:A9)

СУММ(B6:B9)

СУММ(C6:C9)

СУММ(D6:D9)

СУММ(E6:E9)

СУММПРОИЗВ(A1:E4;A6:E9)

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

    В окне диалога Поиск решения:
    Установить целевую ячейку $F$10
    Равной мин имальному значению
    Изменяя ячейки: $А$6:$E$9
    Ограничения:
    $А$10:$E$10=$A$11:$E$11
    $А$6:$E$9>=0
    $F$6:$F$9=$G$6:$G$9

    Щелкните на кнопке Параметры… и установите флажок Линейная модель

    Нажмите кнопку Выполнить

    Оптимальное решение транспортной задачи будет отражено в диапазоне А6:Е9

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

Excel необходимо: ...

  • Задачи линейного программирования. Графический метод решения задач линейного программирования

    Решение

    Microsoft Excel . Решение задач выпуклого программирования при помощи линейной аппроксимации. Приближённое решение задач математического программирования методом сепарабельного программирования . Экономические задачи , решаемые с помощью ...

  • Инструкция по использованию microsoft Excel для решения задач лп 5 3 Одноиндексные задачи лп 6 > 3 Ввод исходных данных 6 > 3 Решение задачи 13

    Инструкция

    1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel ” 1.1. ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном...

  • Некоторые понятия линейного программирования

    Документ

    Мы приведем решение этой задачи с помощью программы Tora. рассмотрим реализацию задачи линейного программирования в... задачи с помощью Microsoft Excel . 1. Осуществляем ввод данных в таблицу Excel (рис. 1). Рис. 1. Заполнение листа для решения задачи ...

    • Цель работы: изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.

    1. Теоретическая часть

    Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .

    Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.

    Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.

    Постановка задачи

    Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.

    Таблица 1

    Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.

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

    Математическая модель задачи

    Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.

    Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции

    F = 240 x 1 + 210 х 2 + 180 x 3

    при ограничениях:

    Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия

    x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.

    Порядок оптимального решения задачи

    Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.

    Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.

    Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.

    Шаг 2. В ячейку E3 вводится формула

    СУММПРОИЗВ(В3:D3; $B$2:$D$2)

    для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.

    Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.

    Таблица 2

    СУММПРОИЗВ(В5:D5; $B$2:$D$2)

    СУММПРОИЗВ(В6:D6; $B$2:$D$2)

    СУММПРОИЗВ(В7:D7; $B$2:$D$2)

    Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.

    В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).

    Затем в этом окне (рис. 3) заполняются следующие поля этого окна:

    В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);

    В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);

    В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.

    В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).

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

    Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.

    После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.

    Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).

    Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.

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

    Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.

    Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).

    Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.

    Таким образом, получено оптимальное решение исходной задачи в виде вектора
    , где
    ,
    и
    , для которого значение целевой функцииF максимально и составляет F * = 129825.

    Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.

    Отчет по результатам для рассмотренной задачи показан на рис. 9.

    В данном отчете представлены оптимальное решение задачи линейного программирования и его расположение в области допустимых решений. В графах Результат выводятся оптимальные значения целевой функции F * и переменных задачи
    , а также их значения для исходного базисного решения, с которого начинался поиск оптимального решения (графаИсходное значение ). Состояние ограничений (графа Статус ) характеризует расположение точки
    в области допустимых решений. ГрафаРазница показывает разности между значениями левых и правых частей ограничений (невязки). Для связанного ограничения невязка равна нулю, что свидетельствует о расположение точки
    на границе области допустимых решений, которая задается этим ограничением. Если ограничение являются не связанным, то оно не влияет на оптимальное решение.

    Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.

    В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.

    В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x 2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x 2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x 2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x 2 увеличить более чем на 150), то неизвестная x 2 в решении будет больше нуля.

    В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.