Три готовых задачи по примеру. Вариант 21

Задача.
Фабрика "GRM pic" выпускает два вида каш для завтрака - "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основ¬ном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.
Управляющему производством необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.
Цех Необходимый фонд рабочего времени, чел.-ч/т Общий фонд рабочего времени
чел.-ч. в месяц
"Crunchy" "Chewy"
А. Производство а11 а12 b1
В. Добавка приправ а21 а22 b2
С. Упаковка а31 а32 b3

Вариант 0: а11 = 10, а12 = 4, а21 = 3, а22 = 2, а31 = 2, а32 = 5, b1= 1000, b2=360, b3 = 600.

Доход от производства 1 т "Crunchy" составляет с1 = 150 у.е., а от производства "Chewy" –с2 = 75 у.е. На настоящий момент нет никаких ограничений на возможные объемы продаж. Имеется возможность продать всю произведенную продукцию.
Требуется:
а) Сформулировать модель линейного программирования, максимизи¬рующую общий доход фабрики за месяц.
б) Решить ее c помощью MS Excel.
Формальная постановка данной задачи имеет вид:
150x1+75x2→max
{█(〖10x〗_1+〖4x〗_2≤1000@〖3x〗_1+〖2x〗_2≤360@〖2x〗_1+〖5x〗_2≤600@x_1≥0@x_2≥0)┤ (1)

Ввод исходных данных
Создание экранной формы и ввод исходных данных
Экранная форма для решения в MS Excel представлена на рисунке 1.

Рисунок 1.
В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (x1), C4 (x2), коэффициентам ЦФ соответствуют ячейки B6 (c1=150), C6 (c2=75), правым частям ограничений соответствуют ячейки D18 (b1=1000), D19 (b2 =360), D20 (b3=600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму
Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ, которая вычисляет сумму попарных произведений двух или более массивов.
Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций", который можно вызвать из меню "Вставка" или при нажатии кнопки " " (рисунок 2) на стандартной панели инструментов.

Рисунок 2
Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D6;
· нажав кнопку " ", вызовите окно"Мастер функций - шаг 1 из 2";
· выберите в окне "Категория" категорию "Математические";
· в окне "Функция" выберите функцию СУММПРОИЗВ (рис. 3);

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

Рисунок 4
Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B13, C13 - 1-е ограничение; B14, С14 - 2-е ограничение и B15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.
Формулы, описывающие ограничения модели (1)
Левая часть ограничения Формула Excel
или =СУММПРОИЗВ(B4:C4;B13:C13))
или =СУММПРОИЗВ(B4:C4;B14:C14))
или =СУММПРОИЗВ(B4:C4;B15:C15)

Задание ЦФ
Дальнейшие действия производятся в окне "Поиск решения", которое вызывается из меню"Сервис" (рис.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) после получения решения

Варианты заданий
№ вар. а11 а12 а21 а22 а31 а32 b1 b2 b3 с1 с2
0 10 4 3 2 2 5 1000 360 600 150 75
10 3 2 3 4 3 1000 360 600 140 65
10 3 3 5 3 2 900 350 400 145 75
7 6 5 4 5 3 920 430 300 150 100
5 7 8 3 4 9 850 300 500 120 80
8 3 7 2 6 4 820 250 200 100 70
9 3 2 2 4 5 920 430 300 140 80
10 2 3 4 3 9 850 300 500 120 80
11 3 2 5 2 5 1100 350 500 150 80
6 5 4 5 3 7 1050 350 500 150 100
7 8 3 4 9 5 950 400 550 120 80
9 7 2 6 4 8 900 300 400 110 70
8 5 3 6 9 2 830 360 350 170 120
9 4 7 5 2 3 800 450 320 210 130
10 3 5 8 2 9 750 400 350 150 100
12 8 4 6 9 2 830 330 200 190 140
9 7 3 2 5 6 930 450 550 90 75
14 5 8 3 2 9 720 300 360 170 100
8 2 3 6 9 5 700 310 300 130 140
13 9 8 2 10 7 850 430 460 170 95
16 2 7 9 3 5 800 370 510 180 120
15 7 3 4 9 2 910 410 450 190 130
10 6 5 7 8 3 790 270 220 130 90
11 3 9 8 4 7 920 260 330 190 120
8 4 10 6 5 3 900 390 430 220 140
12 9 5 4 3 7 740 250 240 130 70
16 5 3 7 9 2 1000 290 390 110 120
9 4 3 6 2 7 780 300 260 190 140
13 9 5 2 6 8 900 310 470 190 80
14 10 7 9 3 2 890 270 380 140 85
7 3 2 9 8 6 850 380 490 200 100
2. Решение задачи о распиле гос. бюджета в Excel

ЗАДАНИЕ.
На лесопилку поступают доски длиной l = 10 м. По контракту лесопилка должна поставить клиенту не менее n1 = 100 досок длиной l1 = 5 м, не менее n2 = 200 досок длиной l2 = 4 м и не менее n3 = 300 досок длиной l3 = 3 м (вариант 0). Как работникам лесопилки выполнить условия контракта, разрезав наименьшее количество досок?

РЕШЕНИЕ.

Составим модель задачи. Найдем все возможные способы распила бревен длиной 10 м на доски длиной 5, 4 и 3 м.
Способы
распила Количество бревен Отходы
5 м 4 м 3 м
1 2 0 0 0
2 1 1 0 1
3 1 0 1 2
4 0 1 2 0
5 0 2 0 2
6 0 0 3 1

Пусть xi бревен распиливается по способу i . Составляем модель задачи:
F = x1 + x2 + x3 +x4 + x5 + x6 → min ,


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





Получаем результаты


Таким образом, нужно распилить 50 бревен по 1 способу, 150 по четвертому способу и 25 по пятому способу. При этом все ограничения будут удовлетворены, а количество бревен будет минимальным и составит 225 штук.

Индивидуальные задания

№ вар. l n1 n2 n3 l1 l2 l3
0. 10 100 200 300 5 4 3
11 30 40 50 3 5 4
12 30 60 80 4 6 3
13 20 50 70 4 3 8
14 50 100 150 3 6 7
15 40 60 80 7 5 4
6 300 100 200 1 5 3
7 50 30 40 3 1 5
8 80 30 60 2 3 4
9 70 20 50 5 2 3
10 150 50 100 5 4 2
11 80 40 60 6 5 4
12 200 300 100 2 6 3
13 40 50 30 4 2 8
14 60 80 30 2 6 7
15 50 70 20 7 5 6
6 100 150 50 5 1 2
7 60 80 40 3 1 5
8 100 200 300 2 3 4
9 30 40 50 5 2 3
15 30 60 80 5 4 3
13 20 50 70 3 5 4
12 50 100 150 2 6 3
13 40 60 80 4 3 8
14 300 100 200 3 6 7
15 50 30 40 7 5 2
6 80 30 60 5 1 2
7 70 20 50 3 1 5
8 150 50 100 2 3 4
9 80 40 60 5 2 3
10 50 100 120 5 1 3


 
3. Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Excel

ЗАДАНИЕ.
Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить a11 кг сырья первого типа, a21 кг сырья второго типа, a31 кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить a12 кг сырья первого типа, а22 кг сырья второго типа, a32 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве b1 кг, b2 кг, b3 кг соответственно. Рыночная цена единицы Изделия 1 составляет c1 тыс. руб., а единицы Изделия 2 – c2тыс.руб. (вариант 0):
а11=2 а12=7 b1=560 c1=55
а21=3 а22=3 b2=300 c2=35
а31=5 а32=1 b3=332

Требуется:
1) построить экономико – математическую модель задачи;
2) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.
3) составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи табличного симплекс – метода решения задачи линейного программирования.
4) составить план производства изделий, обеспечивающий максимальную выручку от их реализации, используя надстройку «Поиск решения» в среде MS EXCEL.