Задачи линейного программирования

Решение оптимизационных задач в среде Excel

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

Склады	Количество товара на складах	Потребители и их заказ

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

Склады	Количество товара на складах	Потребители и их спрос

10.

Склады	Количество товара на складах	Потребители и их спрос

11.

Склады	Количество товара на складах	Потребители и их заказ

12.

Склады	Количество товара на складах	Потребители и их спрос

Задачи линейного программирования

1. Производство угля с определенными свойствами. Предприятие должно поставлять заказчику уголь с содержанием фосфора не более 0,03% и примесью песка не более 3,25%. На складах предприятия имеются три сорта угля со следующими свойствами:

Сорт угля	Содержание фосфора, %	Примесь песка, %	Цена за одну тонну, у. е.
А	0,06	2,0
Б	0,04	4,0
В	0,02	3,0

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

2. Производство изделий. Фирма производит изделия А и Б при неограниченном рынке сбыта. Чтобы изготовить одно изделие, требуются следующие затраты времени обработки на каждом из трех станков:

Изделие	Станок 1	Станок 2	Станок 3
А	0,5 часа	0,4 часа	0,2 часа
Б	0,25 часа	0,3 часа	0,4 часа

Станки имеют определенный недельный ресурс работы: первый станок - не более 40 часов, второй и третий - не более 36 часов каждый. Прибыль предприятия от реализации одного изделия А составляет 5 у. е, одного изделия Б - 3 у. е.

Предложить модель недельного производства изделий А и Б, обеспечивающую фирме максимальную прибыль.

3. Производство полок. Фирма производит две модели книжных полок А и Б при ограниченном количестве сырья и времени изготовления. Для одного изделия модели А требуется 3 м2 досок, а для каждого изделия модели Б - 4 м2. Фирма может получить от поставщиков не более 1700 м2 досок в неделю. Изготовление одной полки модели А требует 12 минут машинного времени, а моде- ли Б - 30 минут. Ресурс машинного времени в неделю - не более 160 часов. Реализация одной полки модели А приносит фирме 20 у. е. прибыли, модели Б - 40 у. е. Рынок сбыта неограничен.

Спланировать производство полок А и Б таким образом, чтобы прибыль фирмой была максимальной.

4. Система рекламы. Фирма рекламирует свою продукцию с помощью телевидения, радио, газет и афиш. Это приводит к увеличению прибыли соответственно на 10, 3, 7 и 4 у. е. на 1 у. е., затраченную на рекламу. Распределение рекламного бюджета имеет следующие ограничения:

а) полный рекламный бюджет не превышает 500 000 у. е.;

б) на телерекламу можно потратить не более 40% всего рекламного бюджета;

в) на радиорекламу должно приходиться не менее 50% от величины затрат на телерекламу;

г) на афишную рекламу можно отвести не более 20% всего рекламного бюджета.

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

5. Разлив молока. Молокозавод имеет две разливные машины: А - для разлива в литровые пакеты и Б для разлива в пакеты по 0,5 литра. Каждая машина может разливать и в пакеты другой емкости, но с потерей производительности:

Машина	Количество пакетов в минуту
0,5 литра	1 литр
А Б

Каждая машина работает по 6 часов в день при пятидневной рабочей неделе. Объем недельной продукции по условиям спроса не превышает 50 000 литров. Рынок принимает не более 44 000 пакетов по 0,5 литра и не более 30 000 литровых пакетов. Прибыль от реализации 0,5-литрового пакета составляет 0,05 у. е., а от реализации литрового пакета - 0,1 у. е.

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

6. Рациональная диета питания. Имеется определенный набор продуктов, основные качества которых, измеренные в относительных единицах, приведены в следующей таблице:

Продукт Содержимое	Хлеб	Соя	Сушеная рыба	Фрукты	Молоко
Белки Углеводы Жиры Витамины
Цена за 1 кг

Составить наиболее дешевый рецепт диеты питания, содержащей не менее 20 единиц белков, не менее 30 ед. углеводов, не менее 10 ед. жиров и не менее 40 ед. витаминов.

7. Производство моющих средств. Моющие средства оценивают по трем основным показателям: очищающему свойству, дезинфицирующему свойству и по раздражающему действию на кожу. Для продажи на рынке моющее средство должно иметь не менее 60 единиц очищающего действия и не менее 60 единиц дезинфицирующих свойств по соответствующей шкале оценок; при этом раздражающее действие должно быть минимальным. Предприятие располагает запасами трех видов очистителей со следующими характеристиками в относительных единицах:

Очиститель	Очищающие свойства	Дезинфицирующие свойства	Раздражающее действие
А Б В

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

8. Урожай. Фермер, имея два участка земли площадями 100 и 70 га, выращивает на них рожь и пшеницу. Урожайность, стоимость и планируемый объем производства зерновых культур приведены в следующей таблице:

Культура	Урожайность, ц/га	Стоимость 1 ц, у. е.	Объем производства
участок	участок
Пшеница Рожь				не менее 1200 ц не менее 400 ц

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

9. Производство обуви. При изготовлении одной из моделей обуви используют две детали: А и Б. Одна и та же деталь может быть изготовлена из различных видов кожи с различной стоимостью. Исходные данные приведены в следующей таблице:

Деталь	Кол-во дета- лей по плану, тыс. шт.	Кол-во деталей, которые можно изготовить из 1 тыс. м2данного вида кожи, тыс. шт.
Вид 1	Вид 2	Вид 3
А Б		20,5	8,7	80,5
Кол-во имеющегося материала, тыс. м2	0,8	0,5	3,6
Стоимость 1 тыс. м2., у. е.		8,5

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

10. Загрузка станков. Механический цех должен выполнить заказ по изготовлению 4000 изделий A и 3000 изделий Б. Для этой цели могут быть использованы три станка, каждый из которых может обрабатывать оба изделия. Известно, что станки имеют следующий запас производственной мощности: 1-й - 120 часов, 2-й - 100 часов, 3-й - 160 часов. Производительность каждого станка (количество изделий, обрабатываемых станком в течение часа), а также себестоимость одного изделия каждого вида при обработке на том или ином станке приведены в следующей таблице:

Изделия	Количество изделий, шт.	Производительность, шт./час / Себестоимость изд., у. е.
Станок 1	Станок 2	Станок 3
А		30 / 6	20 / 8	15 / 11
Б		20 / 12	14 / 10	25 / 7

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

11. План производства. Предприятие должно выпускать два вида продукции, используя при этом последовательно различные группы производственного оборудования. Выпуск одного комплекта продукции A обеспечивает предприятию прибыль 2 млн. руб., продукции B - 3 млн. руб. Фонд времени работы (в днях) каждой группы оборудования и трудоемкость (в днях) изготовления комплектов продукции обоих видов представлены в таблице:

Группа производственного оборудования	Норма времени на выпуск одного комплекта	Фонд времени
А	В
I
II
III
IV

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

12. Откорм свиней. Пусть для откорма свиней есть возможность использовать три различных вида корма. Каждый из видов содержит различное количество питательных веществ (в нашем случае количество компонентов равно четырем). Можно из данных видов корма составить смеси, различающиеся как по питательности, так и по стоимости. Вся информация к задаче представлена в таблице:

Питательные вещества	Единица веса, г	Минимальные суммарные потребности,
Корма 1	Корма 2	Корма 3	г
Вещество 1
Вещество 2
Вещество 3
Вещество 4	0,6	0,25		232,5
Затраты на ед. веса, руб.				-

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

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

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

Вид сырья	Нормы расхода сырья на 1 т карамели, т	Общее количество сырья, т
А	В	С
Сахарный песок	0,8	0,5	0,6
Патока	0,4	0,4	0,3
Фруктовое пюре	-	0,1	0,1
Прибыль, руб.				-

14. Рацион откорма животных. При откорме животных каждое животное должно ежедневно получать не менее 60 ед. питательного вещества А, не менее 50 ед. вещества В и не менее 12 ед. вещества С. Указанные питательные вещества содержат три вида корма. Содержание единиц питательных веществ в 1 кг каждого из видов корма приведено в таблице:

Питательные вещества	Количество единиц питательных веществ в 1кг корма для трех видов корма
I	II	III
А
В
С

Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах, если цена 1 кг корма 1-го вида составляет 9 руб., корма 2-го вида - 12 руб., корма 3-го вида - 10 руб.

15. Мебельная фабрика. Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в таблице.

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

Ресурсы	Нормы затрат ресурсов на одно изделие	Общее количество
Стол	Шкаф	ресурсов
Древесина, м3 I вида II вида	0,2 0,1	0,1 0,3
Трудоемкость, чел.-ч	1,2	1,5	371,4
Прибыль руб.			-

16. Швейная фабрика. На швейной фабрике для изготовления четырех видов изделий может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия приведены в табл. 9. В ней же указаны имеющиеся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида.

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

Артикул ткани	Норма расхода ткани на одно изделие вида, м	Общее количество ткани, м

I		-
II	-
III			-
Цена одного изделия, руб.				-

17. ОТК. В отделе технического контроля (ОТК) некоторой фирмы работают контролеры 1 и 2 разрядов. Норма выработки ОТК за 8-часовой рабочий день составляет не менее 1840 изделий. Контролер 1-разряда проверяет 25 изделий в час, причем не ошибается в 98% случаев. Контролер 2-го разряда проверяет 15 изделий в час, его точность составляет 95%. Заработная плата контролера 1-го разряда 4 рубля в час, контролер 2-го разряда получает 3 рубля в час. При каждой ошибке контролера фирма несет убытка в размере 2 рубля. Фирма может использовать 8 контролеров 1-го разряда и 10 контролеров 2-го разряда.

Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальными.

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

18. Программа выпуска продукции. Предприятие может работать по пяти технологическим процессам (T₁, T₂, T₃, T₄, T₅), причем количество единиц выпускаемой продукции по разным технологическим процессам за 1 ед. времени соответственно равно 300, 260, 320, 400 и 450 шт. В процессе производства учитываются следующие факторы: сырье, электроэнергия, зарплата и накладные расходы. Затраты соответствующих факторов при работе по разным технологическим процессам в течение 1 ед. времени указаны в нижеследующей таблице.

Производственные факторы	Затраты при различных технологиях	Лимит
T₁	T₂	T₃	T₄	T₅
Сырье
Электроэнергия	0,2	0,3	0,25	0,15	0,25
Оплата труда
Накладные расходы

Найти программу максимального выпуска продукции.

19. Производство продукции. Планируется выпустить два вида продукции. Для производства единицы продукции первого вида требуется 2 кг сырья первого вида, 1 кг сырья второго вида. Для производства единицы продукции второго вида требуется 1 кг сырья первого вида, 1 кг сырья второго вида. Наличие сырья первого вида –10 кг; второго – 7 кг. Прибыль от реализации единицы продукции первого вида – 6 рублей; второго вида – 4 рубля.

Разработать оптимальный план выпуска продукции, оптимизирующий прибыль.

20. Производство руды с необходимым содержанием химических элементов. При создании сплава для новой продукции компания Eastern Steel использует железную руду, получаемую с четырех различных шахт. Как показал анализ, чтобы получить сталь с заданными технологическими свойствами, нужно обеспечить содержание основных химических элементов А, В, С в исходном сырье:

Элемент	Минимальное содержание, кг/т
A
B
C

Руда с каждой шахты содержит все три элемента, но в разных количествах. Состав руды приведен в таблице ниже:

Элемент	Шахта (содержание элементов, кг/т)

A
B
C

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

Шахта	Стоимость руды, долл. США

21. Производство стульев. Мебельная фирма производит два вида стульев «Мечта» и «Лада». Компании требуется оптимизировать план недельного производства стульев, исходя из того, что прибыль от продажи одного стула «Мечта» составляет 56 рублей, а от продажи одного стула «Лада» – 40 рублей. Для сборки стульев нужны длинные и короткие штифты, ножки и одно из двух типов сидений. Недельный запас этих изделий на складе ограничен. Данные о потребностях деталей каждого вида для сборки одного стула и запас деталей на складе приведен в таблице.

Наименование детали	Расход на один стул	Общий запас
«Мечта»	«Лада»
Длинные штифты
Короткие штифты
Ножки
Прочные сиденья
Облегченные сиденья

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

Перед менеджерами компании стоит задача определить оптимальный план недельного производства стульев каждого типа.

22. Реклама стирального порошка. Компания, производящая стиральный порошок, хочет выпустить на рынок новый продукт. На рекламную кампанию в первый месяц продвижения продукта на рынок выделено 72 000 долларов. Компания обратилась за помощью в рекламное агентство, которое предоставило следующие данные о воздействии рекламы на целевую аудиторию:

Размещение рекламы	Число единиц товара, купленных благодаря рекламе	Стоимость одного рекламного объявления, долл.
Дневное радио		1 700
Вечернее ТВ		2 800
Ежедневная газета		1 200

Рекламное агентство располагает информацией о снижении степени воздействии рекламы при ее многократном повторении. В частности, в агентстве считают, что на дневном радио эффективность первых 10 рекламных объявлений можно оценить 60 баллами, а всех последующих – 40 баллами. Таблица эффективности рекламных объявлений в различных СМИ приведена ниже.

Размещение рекламы	Первые 10 объявлений	Последующие объявления
Дневное радио (1)
Вечернее ТВ (2)
Ежедневная газета (3)

Фирма-производитель стирального порошка сформулировала и некоторые дополнительные условия: а) в каждом СМИ должно быть размещено не более 25 объявлений; б) общими усилиями всех СМИ объем продаж должен возрасти на 1800 000 единиц товара; в) не менее четверти всех рекламных объявлений должнобыть сделано на вечернем ТВ.

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

	Содержание в 1 унции К	Содержание в 1 унции С	Потребность
Вещество Т	0,10 мг	0,25 мг	1,00 мг
Вещество Н	1,00 мг	0,25 мг	5,00 мг
Калории	110,00	120,00	400,00
Стоимость 1 унции, %	3,8	4,2

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

Компьютер	Прибыль за модель У.е.	Максимальный спрос на товар	Требуется часов на подключение	Требуется часов на сборку	Требуется часов на проверку
Домашний			0,9	1,2	1,3
Игровой			1,1	1,5	1,5
Офисный			0,7	0,9	0,9
Экстрим			1,3	1,1	1,2
Доступно человеко-часов на каждую операцию