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

1-30. Выполнить математическую постановку задач.

 

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

 

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

 

Задача 2.	Для изготовления столов и шкафов применяется три вида древесины. Расход древесины для каждого изделия приведен в таблице.
	Изделие	Вид древесины
	I	II	III
	Стол, м 3	0,2	0,2	0,25
	Шкаф, м 3	0,3	0,25	0,25
	Запасы древесины, м 3

 

Доход от реализации одного стола составляет 30 грн., а шкафа – 42 грн. Поставить задачу математически, максимизируя доход.

 

Задача 3.	Допустимые варианты раскроя длиномерного материала длиной 7,4 м на заготовки размером 1,5; 2,1; 2,9 м представлены в таблице
	Длина заготовок, мм	Число заготовок, выкраиваемых по вариантам
	I	II	III	IV	V	VI
				-		-
		-	-
					-
	Используется мм
	Отход мм

Осуществить раскрой при минимальных отходах материала. Выполнить математическую постановку задачи, учитывая, что заготовок I вида должно быть не меньше 300, II вида – не меньше 420, а III – не меньше 570.

 

Задача 4.	Распределить детали за машинами таким образом, чтобы на их обработку было затрачено минимум времени. Представить задачу математически. В таблице приведены все необходимые данные.
	Деталь машины	Норма времени на обработку	Резерв времени машины
	1	2	3	4	5	6
	Требуемое число деталей

 

Задача 5.	Построить план перегона порожних товарных вагонов из пунктов отправления в пункты назначения, чтобы суммарные затраты на перегон были минимальными. В таблице приведены затраты на перегон одного вагона.
	Пункты назначения Пункты отправления						Избыток
	Потребность в вагонах

 

Задача 6.	Составить оптимальный суточный рацион откорма свиней, если рацион одной головы должен содержать кормовых единиц 2,3 кг, перевариваемого протеина – 270 г, каротина – 48 г. Рацион составляется из трех видов кормов: ячменя, бобов, сенной муки. В 1 кг ячменя содержится кормовых единиц 1,2 кг, перевариваемого протеина – 80 г, каротина – 12 г; в 1 кг бобов соответственно – 1, 25 кг, 280 г и 10 г; в 1 кг сенной муки соответственной 0,75 кг, 100 г и 20 г. Цена 1 кг ячменя – 3 грн, бобов – 14 грн, сенной муки – 8 грн. Критерий оптимальности – минимум стоимости рациона.
Задача 7.	На трех группах оборудования необходимо изготовить изделия четырех видов. Установлен план производства: изделий типа А – 2000 шт., Б – 1000 шт., В – 200 шт., Г – 250 шт. Данные о себестоимости изготовления каждого изделия, трудоемкости и фонда рабочего времени даны в таблице.
	Оборудование	Себестоимость, грн.	Время на одно изделие	Фонд времени, часы
	A	Б	В	Г	A	Б	В	Г
	I
	II
	III

 

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

 

Задача 8.

Арматурный цех завода получает пруток длиной 5 м. Необходимо выпустить 350 заготовок длиной 2,4 м, 500 заготовок длиной 1,6 м и 750 заготовок длиной 1,3 м. Составить различные варианты раскроя и построить модель минимизации отходов при выполнении производственной программы.

 

Задача 9.	На строительном участке имеется 5 экскаваторов, которые могут быть использованы на 5-ти строительных объектах. Себестоимость (грн./час) земляных работ указана в таблице.
	Тип экскаватора	Строительный объект
	1	2	3	4	5
	А
	Б
	В
	Г
	Д

 

Необходимо задачу распределения экскаваторов поставить математически, добиваясь минимальной себестоимости. (Экскаваторы между объектами в течение смены не перемещают).

 

Задача 10.	Предприятие располагает тремя группами оборудования и может выпускать на нем четыре вида продукции. Трудоемкость обработки каждого изделия на различном оборудовании и прибыль приведены в таблице.
	Номер изделия	Трудоемкость обработки по группам оборудования /час	Прибыль за штуку	Минимальный объем реализации, шт.
	I	II	III
	Фонд времени, час				-	-

 

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

 

Задача 11.	Распределить площадь для засева под различные культуры, чтобы валовая продукция в стоимостном выражении была наибольшей. Выразить задачу в математической форме, если в таблице указаны затраты труда на каждую культуру.
	Показатели	Ячмень	Сахарная свекла	Производственные ресурсы
	Затраты на механизированных работах, час	0,6	4,5
	Затраты конно-ручного труда, час
	Цена 1 центнера продукции, грн.			-

Урожайность ячменя составляет 25 ц с гектара, свеклы – 80 ц.

 

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

 

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

 

Задача 13.	Три сорта топлива в количествах 40, 70 и 50 т. распределить между четырьмя агрегатами, потребности которых равны 60, 30, 45 и 25 т. соответственно. Задана матрица теплотворной способности каждого топлива в каждом агрегате:
	.

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

 

Задача 14.	Фабрика выпускает кожаные брюки, куртки, пальто. В процессе изготовления изделия проходят три участка, время обработки и плановая себестоимость изделий приведены в таблице. Ограничения на фонд времени на участках соответственно составляют 4000, 4200 и 4400 часов.
	Показатели	Брюки	Куртки	Пальто
	Норма времени на дубильном участке	0,4	0,5	0,7
	Норма времени на раскройном участке	0,5	0,3	0,8
	Время на пошивочном участке	0,6	0,5	0,8
	Плановая себестоимость, грн.

 

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

 

Задача 15.	Предприятие получает пруток длиной 5 м для изготовления заготовок длиной 1,2 м, 0,8 м и 1,5 м, потребность в которых равна соответственно не менее 800, 950, 1200 штук. Необходимо определить, какое количество прутков и какими способами нужно нарезать заготовки, чтобы отходы были минимальными. Варианты раскроя прутка на заготовки представлены в таблице.
	Размер заготовки	Варианты раскроя
	1,2							-	-
	0,8	-						-
	1,5	-	-	-			-
	Отходы	0,2	0,6	0,2	0,3		0,6	0,5	0,4

 

Задача 16.	Три действующих кирпичных завода А, В и С имеют дневную производительность 80, 120 и 100 тыс. штук кирпича. Планируемая потребность в кирпиче: у потребителя I – 90 тыс. штук, у II – 70 тыс. штук, у III – 80 тыс. штук, у IV – 60 тыс. штук. Матрица транспортных расходов задана.
	Поставщики	Потребитель
	I	II	III	IV
	А
	В
	С

 

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

 

Задача 17.	С трех складов необходимо вывезти минеральную воду в три торговые точки. Стоимость перевозки 1 тыс. бутылок представлена в таблице.
	Пункт отправления	Затраты на доставку 1 тыс. бутылок в торговые точки	Объем вывоза, тыс. бутылок
	Объем ввоза, тыс. бутылок

 

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

 

Задача 18.	Строительные организации сооружают дома четырех различных типов: Д-1, Д-2, Д-3, Д-4. Данные о количестве квартир разного типа в каждом из домов приведены в таблице.
	Показатели	Д-1	Д-2	Д-3	Д-4
	Однокомнатные
	Двухкомнатные смежные
	Двухкомнатные несмежные
	Трехкомнатные
	Четырехкомнатные
	Плановая себестоимость, тыс. грн.

 

Годовой план ввода жилой площади составляет соответственно 1500, 840, 1740, 1950, 650 квартир указанных типов. Составить план строительства жилых домов, чтобы общая себестоимость была наименьшей. Записать задачу в каноническом виде.

 

Задача 19.	Цех мебельного комбината выпускает трельяжи, трюмо и тумбочки под телевизоры. Норма расхода материала, плановый ассортимент и себестоимость изделий приведены в таблице.
	Показатели	Трельяжи	Трюмо	Тумбочки	Запасы древесины
	Расход древесных плит, м3	0,032	0,031	0,038	99,8
	Расход еловых досок, м3	0,020	0,030	0,008	40,8
	Расход березовых досок, м3	0,005	0,005	0,006	15,6
	Плановый ассортимент, штук				-
	Себестоимость, грн.	38,8	64,0	29,6	-

 

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

 

Задача 20.	В соответствии с планируемым уровнем удоя и весом животного одной корове необходимо в сутки не менее 19,26 кормовых ед., 1926 г перевариваемого белка, 114 г кальция и 85 г фосфора. В рацион кормления входят: сено клеверное, сено луговое, кормовая свекла, картофель, силос, концентраты. В таблице приведены показатели, характеризующие содержание питательных веществ в 1 кг корма и цены кормов. Составить рацион, удовлетворяющий требованию минимальной стоимости содержания скота.
	Вид корма	Цена корма, за 1 кг	Потребители
	Кормовые единицы	Белок, г	Кальций, г	Фосфор, г
	Сено клеверное		0,54		9,29	1,95
	Сено луговое		0,52		6,02	2,14
	Силос		0,18		3,55	0,65
	Свекла кормовая		0,12		0,38	0,33
	Картофель		0,30		0,14	0,68
	Концентраты		1,06		2,06	7,60

 

Задача 21.	В состав кормления животных входят три продукта: сено, силос и концентраты, содержащие питательные вещества: белок, кальций и витамины. Содержание питательных веществ и минимально необходимые нормы их потребления заданы таблицей:
	Питательные вещества Продукты	Белок, г/кг	Кальций, г/кг	Витамины, усл.ед./кг
	Сено
	Силос
	Концентраты
	Нормы выдачи

 

Определить оптимальный рацион кормления из условия минимальной стоимости, если цена 1 кг соответственно составляет: сена 3 грн., силоса – 2 грн., концентратов – 5 грн., при предельных нормах суточной выдачи: сена – не более 18 кг., силоса – не более 24 кг и концентратов – не более 16 кг и при содержании питательных веществ в продуктах, указанных в I варианте.

 

Задача 22.	Три вида деталей можно производить на станках разных типов без переналадки. Мощности станков, ограничения на рабочее время и себестоимость в грн. одной детали каждого вида указаны в таблице:
	Вид деталей	Производительность станков, деталей в час	Себестоимость деталей
	I тип	II тип

 

Фонд рабочего времени для станков составляет соответственно 12 и 8 часов. Нужно распределить рабочее время станков в целях получения минимальной себестоимости, если по плану положено за рабочий день выпустить не менее 160 деталей 1 вида и 120 – 2-го вида и не менее 240 – 3-го.

 

Задача 23.	Под посев пшеницы, овса и гречихи отведено два земельных участка площадью в 120 и 150 га соответственно. В таблице указаны: средняя урожайность каждой культуры на каждом участке, выручка грн. на 1 ц культур и варианты плановых заданий по производству.
	Культура	Урожайность по участкам, ц/га	Выручка, грн.	Плановые задания, т
	I вариант	II вариант	I вариант	II вариант
	Пшеница
	Овес
	Гречиха

 

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

2. Как изменится выручка, если установлен II вариант плана?

 

Задача 24.	Издательство, параметры деятельности которого отражены в таблице, выпускает литературу четырех серий.
	Серия Показатель
	Прибыль от реализации ед. продукции, грн./экз.
	Себестоимость ед. продукции, грн./экз.
	Удельная пропускная способность типографии, оттиск/экз.
	Удельный расход бумаги, лист/экз.

Издательство располагает фондом финансовых средств в 10000 грн., лимитами на бумагу в размере 90 000 листов и пропускной способностью типографий, равной 110000 оттисков. При каких тиражах выпускаемых серий издательство получит максимальную прибыль?

 

Задача 25.	Администрация создающегося издательства должна решить вопрос о наборе штата корректоров для каждой из четырех редакций. При этом фонд заработной платы по издательству не должен превзойти 350000 грн., общее время работы всех корректоров не должно превысить 50000 час., суммарный лимит материалов – не более 50000 грн.
	Редакции Показатели	I	II	III	IV
	Заработная плата корректора, грн.
	Затраты времени корректора, час.
	Расход материала на человека, грн.
	Производительность корректора, лист

 

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

 

Задача 26.	Книжный магазин, объем реализации которого не превышает 230000 листов печатной продукции, снабжается четырьмя издательствами. Составляя план-заказ каждому из них, магазин должен учесть лимит затрат на бумагу в 33000 грн. и пропускную способность обслуживающей издательство типографии, равную 100000 листам. Удельные затраты каждого ресурса содержит (по каждому издательству) таблица.
	Издательства Показатели	I	II	III	IV
	Удельный объем книг издательства, листов/книг
	Удельные затраты бумаги, грн./книг
	Удельные типографские затраты, листов/книг
	Прибыль от реализации продукции, грн./книг		4,5		3,5

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

 

Задача 27.	Предприятие располагает ресурсами сырья, рабочей силой и оборудованием, необходимой для производства любого из четырех видов производимой продукции. Затраты ресурсов на изготовление единицы данного вида продукции, прибыль, получаемая предприятием, а также запасы ресурсов указаны в следующей таблице:
	Виды продукции Виды ресурсов					Запасы ресурсов
	Сырье, кг
	Рабочая сила, час.
	Оборудование, станко-час.
	Прибыль на ед. продукции, грн.					-

 

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

 

Задача 28.	Предприятие имеет три комплексные автоматические линии оборудования и может выпускать изделия четырех типов – А, Б, В, Г. Известны средние нормы затрат времени на обработку каждого вида изделий на каждой линии и прибыль от реализации единицы каждого изделия. Необходимые данные приведены в следующей таблице:
	Линии оборудования	Затраты времени на единицу изделия, мин.	Месячный фонд времени, час
	А	Б	В	Г
	I линия	1,0	2,0	4,0	8,0
	II линия	3,0	5,0	1,0	-
	III линия	6,0	-	3,0	1,0
	Прибыль от реализации единицу изделия, грн.					-

 

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

 

Задача 29.	Ткань трех артикулов производится на ткацких станках двух видов с различной производительностью. Для изготовления ткани используется натуральное и синтетическое волокно. В таблице указаны мощности станков (в тыс. станко-час.), ресурсы натурального и синтетического волокна (в тыс. кг), производительности станков по каждому виду ткани (в м/час.), норма расхода волокна по видам (в кг на 1000 м) и цена ткани каждого из артикулов (в грн.) за 1 м.
	Вид ресурса	Объем ресурса	Производительность и нормы расхода
	1	2	3
	Станки I типа		4,0	2,0	5,0
	Станки II типа		1,6	4,0	2,0
	Натуральное волокно		24,0	36,0	42,0
	Синтетическое волокно		2,0	1,0	1,6
	Цена ткани	-

 

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

 

Задача 30.	Мебельная фабрика выпускает столы, стулья, платяные и книжные шкафы. При изготовлении этой продукции используется два типа древесных материалов (досок). В таблице приведены нормативы затрат каждого из материалом (м) и трудовых ресурсов (чел.-час.) на изготовление единицы каждого вида продукции, а также прибыль от реализации единицы изделия и общие объемы наличных ресурсов каждого типа.
	Изделия	Затраты на единицу изделия	Объем ресурсов
	столы	стулья	шкафы платяные	шкафы книжные
	Доски I типа, м
	Доски II типа, м
	Трудовые ресурсы, чел.-час.
	Прибыль, грн.					-

Определить:

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

§ Оптимальный ассортимент при условии, что столов нужно произвести не менее 40, стульев – не менее 120, платяных шкафов – не менее 20 и книжных шкафов – не более 20.

Графический метод

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

1.	2.	3.
4.	5.	6.
7.	8.	9.
10.	11.	12.
13.	14.	15.
16.	17.	18.
19.	20.	21.
22.	23.	24.
25.	26.	27.
28.	29.	30.