Задача 1.2
Цех хлебозавода по производству мукизаключил контракт с мини-пекарней о поставке ежедневно 300 кг ржаной ипшеничной муки, причем пшеничной — не менее 50%. Зерно, поступающее в цех,проходит в нем обмолот, помол и упаковку муки. Трудозатраты (в человеко-часах)на указанные операции представлены в таблице:Операция Ржаная мука Пшеничная мука Имеющийся ресурс Обмолот 0,1 0,1 30 Помол 0,1 0,08 27 Упаковка 0,05 0,05 200
Себестоимость одного килограммаржаной муки составляет 14 рублей, а пшеничной — 18 рублей.
Требуется найти оптимальный планпроизводства продукции, позволяющий цеху выполнить условия контракта снаименьшими затратами.
Решение.
Пусть x1 — объем производства ржаной муки, x2 — объем производства пшеничной муки. Тогда задача может бытьописана в виде следующей модели линейного программирования:
/>
Заполним данные в среде Microsoft Excel
/>
Добавим в таблицу еще одну строку(например, строку 9 План), в которую будут вноситься получаемые в ходе решениярезультаты. Объем производства ржаной муки будем предполагать получить в ячейкеВ9, пшеничной муки — в ячейке С9, а затраты на себестоимость — в ячейке D7.
Для решения задачи необходимо такжевыделить столбец (в данном примере — столбец D), в который будут введены формулы для расчета значений левойчасти ограничений. Формула вводится также и в ячейку, в которой будет рассчитанызатраты на себестоимость предприятия (ячейка D7). Нужно обратить внимание на то, что в формулах используютсяне числа или символьные обозначения, а координаты ячеек таблицы, в которыххранятся эти числа и переменные.
/>
D3= СУММПРОИЗВ(B3:C3;$B$9:$C$9)
D4= СУММПРОИЗВ(B4:C4;$B$9:$C$9)
D5= СУММПРОИЗВ(B5:C5;$B$9:$C$9)
D7= СУММПРОИЗВ(B7:C7;$B$9:$C$9)
D9=B9+C9
Для запуска процедуры оптимизации вменю Сервис необходимо выбрать пункт Поиск решения. В поле Установить целевуюячейку вводятся координаты ячейки (D7), которую необходимо минимизировать.
В поле Изменяя ячейки вводятсякоординаты ячеек (разделенные запятыми или объединенные в интервал двоеточием),в которых содержатся значения переменных — объемов производства ржаной ипшеничной муки. Изменяемые ячейки должны быть прямо или косвенно связаны сцелевой ячейкой. В поле Ограничения необходимо ввести все граничные условиязадачи:
/>
При этом ограничения нанеотрицательность переменных можно ввести путем установки флажка Неотрицательныезначения в окне Параметры. В случае, если решаемая задача является задачейлинейного программирования, лучше отметить это в окне Параметры соответствующимфлажком:
/>
Запуск процесса оптимизациипроизводится нажатием кнопки Выполнить. По окончании счета появляетсядиалоговое окно Результаты поиска решения. Нажав в нем соответствующую кнопку,можно сохранить найденное решение или восстановить исходные значения. Измененияпри этом коснутся как целевой ячейки, так и влияющих ячеек. В этом жедиалоговом окне можно указать необходимые типы отчетов, которые будут размещенына отдельных листах книги.
Отчет Результаты отражает исходные ирезультирующие значения целевой и влияющих ячеек, а также сведения о наложенныхограничениях.
/>
/>
Таким образом предприятию необходимовыпустить 150 кг ржаной муки и 150 кг пшеничной муки, тогда минимальнаясебестоимость выпуска составит 4800 человеко-часов, при этом ресурсы на обмолоти помол будут использованы полностью, а ресурсы на упаковку останутся в избыткев количестве 185 человеко-часов.
Задача 2.2
Руководство птицефабрики имеетвозможность закупать корма трех видов. Из этих кормов птицы должны получатьпитательные вещества (П1, П2, П3 и П4), требуемое количество которых исодержание в кормах (в ед.) приведены в таблице:
Питательные
вещества Корма Нормы потребления К1 К2 К3 П1 3 5 равно 16 П2 2 2 4 не менее 24 П3 8 1 2 не менее 25 П4 4 3 5 не менее 33, но не более 40
Цены за 1 т кормов составляютсоответственно 1000, 900 и 800 рублей.
Какие корма и в каком количествеследует закупать, чтобы затраты птицефабрики оказались минимальными?
Решение.
Решение: обозначим за x1 количество корма К1, за x2 — количество корма К2, за x3 — количество корма К3. Тогда:
/>
Подготовим в Microsoft Excel таблицу для решения задачи:
/>
Поскольку Microsoft Excel позволяет путем установки соответствующего флажкаавтоматически определять неотрицательность переменных, добавление ограниченийна неотрицательность в модель при решении задачи в Microsoft Excel не является обязательным.
Введем в таблицу формулы для расчеталевых частей ограничений и целевой ячейки:
Е4=СУММПРОИЗВ(B4:D4;$B$12:$D$12)
Е5=СУММПРОИЗВ(B5:D5;$B$12:$D$12)
Е6=СУММПРОИЗВ(B6:D6;$B$12:$D$12)
Е7=СУММПРОИЗВ(B7:D7;$B$12:$D$12)
Е8=СУММПРОИЗВ(B8:D8;$B$12:$D$12)
Целевая ячейкаЕ10=СУММПРОИЗВ(B10:D10;$B$12:$D$12)
Ограничения запишутся так
/>
Запустим модуль Поиск решения ипроизведем расчеты
/>
В ходе расчетов получим следующиерезультаты: оптимальный рацион должен содержать 3,125 ед. корма К1, 4,6875 ед.корма К2 и 0,1875 корма К3. При этом стоимость рациона будет составлять 7493,75руб.
Задача 3.1
Один из цехов фабрики по пошивуизделий из кожи раскраивает поступающие заготовки для получения 5 видов деталейодним из трех возможных способов. Из одной заготовки получают:Способ раскроя Детали A B C D E I 10 5 3 7 2 II 6 8 4 5 2 III 4 7 5 3 4
Требуется получить не менее 48деталей вида А, не менее 32 деталей вида В, не менее 45 деталей вида С, неменее 17 деталей вида D и неменее 24 деталей вида Е.
Какое минимальное количествозаготовок нужно раскроить?
Решение.
Обозначим за x1 количество заготовок, разрезаемых по способу 1, за x2 — количество заготовок, разрезаемых по способу 2 ит.д.Используя модель линейного программирования с минимизацией расходаматериала, получим:
/>
Подготовим таблицу в Microsoft Excel,содержащую исходные данные задачи, введем формулы для расчета целевой функции илевой части ограничений, заполним форму модуля Поиск решения:
/>
/>
/>
Решение
/>
Таким образом, необходимораскроить 1 заготовку способом I, 1заготовку способом II, 8 заготовокспособом III.
Задача 4.2
Гражданин О. Бендер хочет приобрестинекий мебельный гарнитур, стоимость которого 100 тыс. рублей. Администрацияаукциона согласна на выплату в рассрочку, с условием, что 20 тыс. руб. О.Бендер выплатит через 2 месяца, а остальную сумму — через 4 месяца.
Однако О. Бендер, справедливополагая, что найти требуемую сумму ему не удастся, хочет получить средствапутем вложения денег по одному из типов вклада: А (сроком на 1 месяц под 1,5%),В (сроком на 2 месяца под 3,5%) или С (сроком на 4 месяца под 8%).
Какую сумму и по какому типу вкладанужно вложить О. Бендеру, чтобы через 4 месяца купить гарнитур?Тип вклада Срок вклада (мес.) Процент по вкладу A 1 1,5 B 2 3,5 C 4 8,0
Необходимо минимизировать размерцелевого фонда.
Решение:
Составим таблицу, отражающуювозможности вложения и возврата денег по месяцам:Вклады 1 2 3 4 5 A1 1®® 1,015 A2 1®® 1,015 A3 1® 1,015 A4 1®® 1,015 B1 1®® ®®® 1,035 B3 1®® ®®® 1,035 C1 1®® ®®® ®®® ®®® 1,08
где: Ai — размер вклада типа A в месяце i; Bi — размер вклада типа B в месяце i; Ci — размер вкладатипа C в месяце i;
Задача может быть описана следующеймоделью:
/>
/>
Функция minimize возвращает вектор значенийпеременных, являющихся аргументами целевой функции, при которых ее значениебудет минимальным. В первой колонке – порядковый номер переменной, начиная снулевого, по очередности упоминания. Во второй – соответствующие значенияпеременных.
При необходимости, присвоивпеременным полученные значения, можно рассчитать и значение целевой функции.
Задача 5.2
Четыре фермерских хозяйства,находящиеся в Рязанской, Владимирской, Тверской и Смоленской областях,направляют выращиваемые овощи и фрукты на переработку и консервацию на один изтрех заводов, которые расположены в Москве, Туле и Ярославле.
Затраты на перевозку 1 т продукциипредставлены в таблице (в рублях): Москва Тула Ярославль Рязанское 500 700 800 Владимирское 400 800 300 Тверское 400 700 400 Смоленское 600 600 700
В сезон Рязанское хозяйствопроизводит 40 т продукции в неделю, Владимирское — 50 т, Тверское — 60 т,Смоленское — 70 т, в то время как завод в Москве может переработать в неделю100 т продукции, в Туле — 50 т, в Ярославле — 40 т.
Составьте план перевозок продукции изфермерских хозяйств на заводы с минимальными транспортными расходами, учитывая,что в связи с ремонтом трассы Москва-Рязань в неделю по ней можно перевезти неболее 20 т продукции.
Решение:
В данной задаче количество выращиваемыхпродуктов, на 30 т больше, чем могут переработать заводы. Сведем задачу кзамкнутому виду, добавив фиктивного пятого поставщика.
Модель рассматриваемой задачивыглядит так:
/>
Заметим, что в целевую функцию невведены штрафы за нереализацию продукции в связи с их отсутствием в условиизадачи.
Для того, чтобы удовлетворитьтребованию /> вместо Московского заводавведем двух других.
Один из них, под именем Московскогозавода будет иметь потребности, то есть возможности в переработке в количестве20 т и с теми же стоимостями перевозок, а второй с возможностью 100 – 20 = 80 ис теми же стоимостями перевозок, за исключением с15, которую примемравной сколь угодно большому числу, например, 1000000000.
После нахождения оптимального планаобъемы перевозок в Москву необходимо прибавить к объемам перевозок Потребителя 2
В результате исходная задача приметвид
Москва Тула Ярославль Потребитель 1 Потребитель 2 Ресурсы Рязанское 500 700 800 10000000000 40 Владимирское 400 800 300 400 50 Тверское 400 700 400 400 60 Смоленское 600 600 700 600 70 Потребности 20 50 40 30 80 220
Решим задачу при помощи модуля Поискрешения:
/>
Целевая ячейка D19 =СУММПРОИЗВ(B2:F5;B12:F15)
/>
/>
Получаем решение
/>
С учетом ограничений на трассуМосква-Рязань окончательно получаем план перевозок Москва Тула Ярославль Рязанское 20 Владимирское 10 40 Тверское 60 Смоленское 10 50
И окончательную стоимость
20*500+10*400+60*400+10*600+50*600+40*300= 86000 у.е.
Задача 6.2
Фирма получила заказ на срочный переводчетырех книг с итальянского языка. Фирма может располагать услугами 5переводчиков, способных выполнить работу такого уровня. Время в днях, закоторое каждый переводчик справится с работой, приведено в таблице: Книга 1 Книга 2 Книга 3 Книга 4 Иванов 10 25 14 25 Петров 8 12 16 28 Сидоров 12 18 17 33 Андреев 14 23 15 30 Васильев 11 20 18 28
Фирма использует повременную оплатутруда. Переводчики имеют разную квалификацию, поэтому за день работы фирмаплатит Иванову 700 рублей в день, Петрову — 800 рублей в день, Сидорову — 600,Андрееву — 500, Васильеву — 550. Поскольку по оценке фирмы качество переводов витоге будет примерно одинаковым, руководство фирмы просит Вас составить такоераспределение работ, которое позволит минимизировать затраты на переводы.
Решение.
Составим модель линейногопрограммирования, отражающую условие:
/>
Решим задачу при помощи Microsoft Excel:
/>
При решении задач о назначении особыйинтерес вызывает способ ввода ограничений при заполнении формы модуля Поискрешения и формулы целевой функции:
/>
/>
/>
Проведенные расчеты показывают, чтоминимальное общие затраты на перевод составили 48800 рублей. Назначение переводчикадля перевода книги определяется наличием на пересечении строки и столбцазначения 1.
Книгу 1 — Петров
Книгу 2 — Иванов
Книгу 3 — Васильев
Книгу 4 — Андреев