Варианты задач линейного программирования

Задача 1.

В трех пунктах отправления A, B, C сосредоточен однородный товар. Этот товар необходимо перевезти в четыре пункта назначения P, Q, R, S. Запасы товара в пунктах отправления и потребности пунктов назначения показаны в таблице.

Запасы (тонн)			Потребности (тонн)
A	B	C	P	Q	R	S
42	36	40	26	41	25	31

Стоимости перевозок 1 т. груза из i-го пункта отправления в j-й пункт назначения заданы матрицей.

	A	B	C
P	200	400	300
Q	700	500	800
R	600	900	700
S	550	430	650

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

2. Решить предыдущую задачу для случая, когда потребность в товаре в пункте Q составляет 20 тонн.

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

Задача 2.

Радиозавод выпускает магнитофоны двух моделей: A и B. Завод должен выпускать в месяц не менее Y_a и Y_b магнитофонов. Каждая модель приносит доход в размере S_a и S_b рублей. Процесс производства магнитофонов состоит из трех стадий: изготовления деталей, сборки изделия и его упаковки. Нормативы времени на эти стадии заданы матрицей T. Производственные мощности завода позволяют расходовать в месяц не более 600 часов на выпуск деталей, 500 часов на сборку магнитофонов и 200 часов на упаковку. Составить план выпуска магнитофонов, обеспечивающий заводу максимальный доход. Определить, какая из стадий в наибольшей степени сдерживает рост производства.

Sa	Sb	Ya	Yb	T (час./1 шт.)
				Модель	Стадия 1	Стадия 2	Стадия 3
40	60	400	600	1 2	0.3 0.35	0.4 0.5	0.1 0.15

Задача 3.

Акционерное общество может возделывать на поле площадью S га. четыре культуры. Наиболее трудоемким этапом является уборка урожая, которая должна осуществляться в два этапа: сначала убираются 1-я и 2-я культуры, а затем 3-я и 4-я. Трудоемкости уборки каждой культуры составляют соответственно Т₁, Т₂, Т₃ и Т₄ человеко-часов на 1 га. Для уборки общество может выделить R₁ человеко-часов на 1-й этап и R₂ на 2-й. Составить план посева культур, даюший максимальную прибыль, если 1 га каждой из культур (при ожидаемой урожайности) приносит прибыль соответственно в С₁, С₂, С₃, С₄ (тыс.руб.). Определить, какой из этапов уборки ограничивает рост прибыли.

S	T1	T2	T3	T4	R1	R2	C1	C2	C3	C4
400	100	150	200	90	25000	30000	400	500	820	300

Задача 4.

Рацион стада крупного рогатого скота из 220 голов включает пищевые продукты А, В, С, D и Е. В сутки одно животное должно съедать не менее 2 кг продукта вида A, 1,5 кг продукта В, 0,9 кг продукта С, 3 кг продукта D и 1,8 кг продукта E. Однако в чистом виде указанные продукты не производятся. Они содержатся в концентратах К-1, К-2 и К-3. Их цена соответственно 0,5; 0,4; 0,9 руб. за килограмм. Содержание продуктов в килограмме концентрата (в %) указано в таблице.

Концентраты	Продукты
	A	B	C	D	E
К-1 К-2 К-3	15 19 5	22 17 12	0 0 25	0 14 5	4 7 8

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

Задача 5.

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

Наименование сырья	Нормы расхода (кг./кг.)
	A	B	C
Сахарный песок	0.6	0.5	0.6
Патока	0.4	0.4	0.3
Фруктовое пюре	0.1	0.2	0.2

Запасы сырья на складе соответственно равны V₁, V₂ и V₃ кг. Прибыль от реализации 1 кг. продукции каждого вида определяется значениями P_A, P_B и P_C. Найти план производства карамели, обеспечивающий максимальную прибыль. Выяснить, какое сырье ограничивает рост прибыли.

Запасы сырья (кг.)			Прибыль от реализации ( руб./кг.)
V1	V2	V3	PA	PB	PC
800	600	120	1.08	1.12	1.28

Задача 6.

Мебельная фабрика выпускает столы, стулья, кресла и кровати. При изготовлении этих товаров используется два вида досок. Запасы досок и трудовых ресурсов показаны в таблице.

Ресурсы
Доски 1 типа (м)	Доски 2 типа (м)	Трудовые (чел.-час.)
1500	1000	1500

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

Изделия	Нормы расхода
Ресурсы	Столы	Стулья	Кресла	Кровати
Доски 1 типа (м)	5	1	9	12
Доски 2 типа (м)	2	3	4	6
Трудоемкость (чел.-час.)	3	2	5	10
Прибыль ( руб.)	12	5	15	18

С учетом спроса на товары фабрика должна выпустить не более 10 кроватей, а соотношение столов и стульев должно быть 1:6.

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

Задача 7.

Полуфабрикат поступает на фабрику в виде двух партий листов фанеры. Первая партия содержит 400 листов, вторая - 250 листов. Из этой фанеры необходимо производить комлекты деталей: 1 комплект содержит 4 детали 1-го типа, 3 детали 2-го и 3 детали 3-го типа. Листы фанеры можно раскраивать различными способами. Количество деталей, которое можно получить из 1 листа фанеры показано в таблице.

1 партия				2 партия
Деталь	Способ			Деталь	Способ
	1	2	3		1	2
1	0	6	9	1	6	3
2	4	3	4	2	5	4
3	10	16	0	3	8	0

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

Задача 8.

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

Вид ресурса	Обьем ресурсов	Производительность и норма расхода
		Артикул 1	Артикул 2	Артикул 3
Станки 1 типа	29000 часов	20 м/час.	10 м/час	25 м/час
Станки 2 типа	30000 часов	8 м/час	20 м/час	10 м/час
Пряжа (кг)	30000кг	0.12 кг/м	0.18 кг/м	0.21 кг/м
Красители (кг)	3000 кг	0.01 кг/м	0.005 кг/м	0.008 кг/м
Цена 1 м ткани (руб.)		45	45	60
Себестоимость 1 м ткани (руб)		24	20	40

Задача 9.

Нефтеперерабатывающий завод имеет запасы 4-х полуфабрикатов: алкилата (S₁); крекинг-бензина (S₂); бензина прямой перегонки (S₃) и изопентона (S₄). В результате смешивания этих компонентов в различных пропорциях, получают 3 сорта авиационного бензина: A, B и C. Запасы сырья, состав бензина и себестоимость его производства даны в таблице.

Запасы сырья (л)				Состав бензина S1:S2:S3:S4
S1	S2	S3	S4	A		B		C
200000	300000	300000	150000	2:3:5:2		3:1:2:1		2:2:1:3
Прибыль от 1 тыс. л бензина (руб)					1200		1000		1500

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

Задача 10.

Оптовая база занимается закупкой и продажей сезонного товара. Одновременно на базе может храниться до 100 единиц товара. Закупка товара на очередной квартал осуществляется в конце предыдущего квартала. К началу первого квартала на складе имелось 30 ед. товара. Цены приобретения и продажи единицы товара по кварталам показаны в таблице.

Цена приобретения на ...				Цена продажи в ...
1 кв.	2 кв	3 кв	4 кв	1 кв.	2 кв	3 кв	4 кв
350	500	500	400	500	600	750	550

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

Задача 11.

Цех мебельного комбината выпускает трельяжи, трюмо и тумбочки под телевизоры. Норма расхода материала в расчете на одно изделие, плановая себестоимость, оптовая цена предприятия, плановый (месячный) ассортимент и трудоемкость единицы продукции приведены в таблице. Запас древесностружечных плит, досок еловых и березовых 90, 30 и 14 м³ соответственно. Плановый фонд рабочего времени 16800 человеко-часов.

Показатели	Трельяжи	Трюмо	Тумбочки
Норма расхода материала, м^3 древесностружечные плиты. доски: еловые ...... березовые ..... Трудоемкость, чел.-ч. .... Плановая себестоимость, руб. Оптовая цена предприятия, руб. Плановый ассортимент, шт. .	0,032 0,020 0,005 10,2 88,81 93,00 350	0031 0,020 0,005 7,5 63,98 67,00 290	0,038 0.006 0,006 5,8 29,60 30,00 1200

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

Задача 12

Фабрика выпускает кожаные брюки, куртки и пальто специального назначения в ассортименте, заданном отношением 2:1:3. В процессе изготовления изделия проходят три производственных участка—дубильный, раскройный и пошивочный. Фабрика имеет практически неограниченную сырьевую базу, однако сложная технология предъявляет высокие требования к квалификации рабочих. Численность их в рамках планируемого периода ограничена.

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

Показатели	Брюки	Куртки	Пальто
Норма времени на участках, чел.-ч дубильном раскройном пошивочном Полная себестоимость, руб. Оптовая цена предприятия, руб.	0,3 0,4 0,5 15 17,5	0,4 0,4 0,4 40,5 42	0,6 0,7 0,8 97,8 100

Ограничения на фонд времени для дубильного, раскройного, и пошивочного участков составляют соответственно 3360, 2688 и 5040 ч.

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

Задача 13

На приобретение оборудования для нового производственного участка выделено 300 тыс. руб. Его предполагается разместить на площади 45 кв. м. Участок может быть оснащен оборудованием трех видов — машинами стоимостью 6 тыс. руб. (здесь и далее все показатели приводятся на единицу оборудования), размещающимися на площади 9 кв. м, производительностью 8 тыс. единиц продукции за смену; машинами стоимостью 3 тыс. руб., занимающими площадь 4 кв. м, производительностью 4 тыс. единиц продукции за смену; машинами стоимостью 2 тыс. руб. Занимаемая ими площадь 3 кв. м, производительность 3 тыс. единиц продукции.

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

Задача 14

В плановом году строительные организации города переходят к сооружению домов типов Д-1, Д-2, Д-3 и Д-4. Данные о количестве квартир разного типа в каждом из указанных типов домов, их плановая себестоимость приведены в таблице. Годовой план ввода жилой площади составляет соответственно 800, 1000, 900, 2000 и 7000 квартир указанных типов.

Показатели	Д-1	Д-2	Д-3	Д-4
Типы квартир однокомнатные	10	18	20	15
двухкомнатные: смежные	40		20
несмежные		20		60
трехкомнатные.	60	90	10
четырехкомнатные	20	10		5
Плановая себестоимость, тыс. руб.	830	835	360	.450

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

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

Задача 15

Предприятие выпускает обычный, специальный и декоративный сплавы латуни и реализует их соответственно по 3; 4, 5 и 6 руб. за единицу веса. Его производственная мощность позволяет производить (за плановый период) не более 500 ед. веса обычного сплава, 700 ед. специального и 250 ед. декоративного. Обязательными составляющими сплавов являются медь, цинк, свинец и никель. Их цена соответственно 0,9; 0,7; 0,5 и 1,1 руб. за единицу веса.

По технологии декоративный сплав должен содержать не менее 7% никеля, 49% меди и не более 29% свинца; специальный—не менее 3% никеля, 71% меди, 9% цинка и не более 21% свинца. В обычный сплав составляющие входят без ограничений.

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

Задача 16

На заводе ежемесячно скапливается около 14 т отходов металла, из которого можно штамповать большие и малые шайбы. Месячная потребность завода в больших шайбах 600 тыс. шт., в малых  1100 тыс. шт. Расход металла на тысячу больших шайб  22 кг, на тысячу малых  8 кг. Для изготовления шайб используются два пресса холодной штамповки. Производительность каждого за смену 9 тыс. шт. больших шайб либо 11,5 тыс. шт. малых. Завод работает в две смены.

Недостающее количество шайб закупается. Оптовая цена больших шайб 11,9 руб. (за тысячу штук), а малых  5,2 руб. Определить месячный план производства шайб, обеспечивающий максимальную долю в валовой продукции предприятия.

Задача 17

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем производства первой линии – 60 изделий, второй линии – 75 изделий. На радиоприемник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприемник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприемника первой и второй моделей равна 30 и 20 долл., соответственно.

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

Задача 18.

Фирма имеет возможность рекламировать свою продукцию, используя местное радио и телевидение. Затраты на рекламу в бюджете фирмы ограничены суммой $ 1000 в месяц. Каждая минута радиорекламы обходится в $ 5, а каждая минута телерекламы – в $ 100. Фирма хотела бы использовать радиосеть, по крайней мере, в два раза чаще, чем телевидение. Опыт прошлых лет показал, что объем сбыта, который обеспечивает каждая минута телерекламы, в 25 раз больше объема сбыта, обеспечиваемого одной минутой радиорекламы.

Определить оптимальное распределение ежемесячно отпускаемых средств между радио- и телерекламой.

Задача 19

Фирма производит два вида продукции – А и В. Объем сбыта продукции А составляет не менее 60% общего объема реализации продукции обоих видов. Для изготовления продукции А и В используется одно и то же сырье, суточный запас которого ограничен величиной 100 кг. Расход сырья на единицу продукции А составляет 2 кг, а на единицу продукции В – 4 кг. Цены продукции А и В равны 20 и 40 долл., соответственно.

Определить оптимальное распределение сырья для изготовления продукции А и В.

Задача 20

Завод получает 4 вида полуфабрикатов В_i в количествах: В₁ – 400 т, В₂ – 250 т, В₃ – 350 т и В₄ – 100 т. В результате смешения этих компонентов получают 3 вида продукции А_j. Пропорции смешиваемых полуфабрикатов следующие: для А₁ – 2:3:5:2, для А₂ – 3:1:2:1, для А₃ – 2:2:1:3. Стоимость 1 т продукции А_j составляет: А₁ – 1200 руб., А₂ – 1000 руб., А₃ – 1500 руб.

Составить оптимальный план выпуска продукции по критерию:

1) максимальной стоимости выпущенной продукции;

2) максимального использования полуфабрикатов.

Задача 21. На заготовительный участок поступили стальные прутья длиной 111 см. Необходимо разрезать их на заготовки по 19, 23 и 30 см. Этих заготовок требуется, соответственно, 311, 215 и 190 шт. Построить экстремальную задачу выбора варианта выполнения этой работы, при котором число разрезаемых прутьев минимально.

Задача 22. На заготовительный участок поступило 69 металлических прутьев длиной 107 см. Их необходимо разрезать на заготовки по 13, 15 и 31 см в комплектности, задаваемой отношением 1:4:2. Построить модель, на основе которой можно сформулировать экстремальную задачу максимизации комплектов заготовок.

Указание к задачам 29, 30. Стандартная методика решения задач раскройного типа заключается в составлении возможных вариантов раскроя (для этого оформляется отдельная таблица) и постановке экстремальной задачи выбора их наилучшей комбинации по заданному критерию.

Литература:

4. Информатика. Базовый курс. Под ред. Симановича С.В. – СПб: «Питер», 2003.

5. Могилев А.В. , Пак Н.И. , Хеннер Е.К. Информатика: Учеб. Пособие для студ. / Под ред. Е.К.Хеннера. – М.: «Академия» , 2001.

6. В.Ф.Ляхович, С.О.Крамаров Основы информатики: Учеб. пособие для студ. / под ред. В.Ф.Ляховича. – Д:изд-во «Феникс» , 2003.