Упражнения для самостоятельной работы

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

Составить математическую модель и решить симплекс-методом:

1. Механический цех выпускает три вида взаимозаменяемых деталей А, В, С, каждая из которых проходит последовательно обработку на трех станках. Запас мощности станков (то есть рабочее время станка) составляет соответственно 110, 200 и 50 часов. Деталь А обрабатывается первым станком 6 мин, вторым – 7,5 мин, третьим - 8 мин; деталь В - соответственно 5, 9 и 2 мин, а деталь С – 4,5, 10 и 2 мин. Отпускная цена промышленности составляет за деталь А - 15 тыс. руб., деталь В - 16 тыс. руб. и деталь С - 14 тыс. руб.

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

2. На швейной фабрике для изготовления четырех видов изделий (I, II, III и IV) может быть использована ткань трех артикулов (А, B и C). Нормы расхода тканей всех артикулов на пошив одного изделия такие: на изделие
I - 2 м ткани артикула А и 8 м - артикула C; на изделие II - 2 м ткани артикула B и 4 м - артикула C; на изделие III - 4 м ткани артикула А и 6 м - артикула B; на изделие IV - 2 м ткани артикула А, 4 м -артикула Б и 8 м - артикула C. В распоряжении фабрики имеется 360 м ткани артикула, артикула B - 420 м и артикула C - 1600 м.

На основе этих данных требуется определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной, если цена одного изделия I составляет 180 руб., II - 120 руб., III - 5 руб. и IV - 14 руб.

3. Цех выпускает четыре вида взаимозаменяемых деталей I, II, III, IV каждая из которых проходит последовательно обработку на трех станках. Запас мощности станков (то есть рабочее время станка) составляет соответственно 210, 150 и 70 часов. Деталь I обрабатывается первым станком 6 мин, вторым 7,5 мин, третьим - 8 мин; деталь II - соответственно 5, 9 и 2 мин, деталь III - 4,5, 10 и 2 мин, а деталь IV - 5, 10,5 и 3 мин. Отпускная цена промышленности составляет: за деталь I - 7,5 тыс. руб., деталь II - 2,6 тыс. руб., деталь III - 8 тыс. руб. и деталь IV - 1,4 тыс. руб.

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

4. Имеется три вида сырья - В 1, B 2, В 3, которые используются для производства двух видов продуктов - А 1 и А 2. В распоряжении предприятия находятся 500 единиц сырья В 1, 750 единиц сырья B 2 и 200 единиц сырья В 3. На производство единицы продукта А 1 расходуется 1 единица сырья В 1 и
2 единицы сырья B 2. На производство единицы продукта А 2 расходуется
2 единицы сырья В 1, 1 единица сырья B 2 и 1 единица сырья В 3. Доход от реализации единицы продукта А 1 составляет 4 руб., а единицы продукта А 2 - 5 руб. Сколько единиц каждого вида продукции необходимо производить, чтобы прибыль была максимальной?

5. Необходимо составить наиболее дешевую смесь из трех веществ. В состав смеси должно входить не менее 6 единиц химического вещества A, не менее 8 единиц вещества B и не менее 12 единиц вещества C. Имеется три вида сырья (М 1, М 2, М 3), содержащих эти химические вещества в пропорциях, указанных в табл. 3.9. Стоимость одной весовой единицы сырья М 1 - 2 руб., сырья М 2 - 3 руб., сырья М 3 - 2,5 руб.

Таблица 3.9

	А	В	С
М1
М2
М3		1.5

6. Для нарезки заготовок длиной 20, 25 и 30 см используются прутки длиной 75 см. За смену требуется нарезать следующее количество заготовок: длиной 20 см - 300 штук., длиной 25 см - 270 штук, длиной 30 см - 350 штук. Из одного прутка можно нарезать заготовки различной длины. Количество заготовок, которое можно нарезать из одного прутка по различным вариантам разрезки, приведено в табл. 3.10. При каждом варианте нарезки будут оставаться концевые остатки, величины которых (в сантиметрах) также приведены в табл. 3.10.

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

Таблица 3.10

№ заготовки	Длина заготовки, см	Вариант раскроя 1 2 3 4 5 6
		3 1 1 0 2 0
		0 2 1 0 0 3
		0 0 1 2 1 0
	Остаток	15 5 0 15 5 0

7. Хозяйство располагает следующими ресурсами: площадь - 100 единиц, труд - 120 единиц, тяга - 80 единиц. Хозяйство производит четыре вида продукции: Р 1, Р 2, Р 3, Р 4. Затраты на производство единицы каждого вида продукции и доход от их производства указаны в табл. 3.11.

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

Таблица 3.11

Продукция	Площадь	Труд	Тяга	Доход
Р 1
Р 2
Р 3
Р 4

Контрольные вопросы для самопроверки

1. Что называется математической моделью оптимизационной задачи?

2. Как классифицируются оптимизационные задачи по виду целевой функции и/или системы ограничений?

3. Что называется критерием оптимальности?

4. Какие методы оптимизации вы знаете?

5. Что называется задачей линейного программирования?

6. Какие основные формы записи задачи линейного программирования существуют? Как перейти от одной формы записи задачи к другой?

7. В чем заключается алгоритм симплекс метода?

8. Какие переменные называются базисными?

9. Как проверить опорный план на оптимальность?

10. Как определить вектор для включения в базис? Как определить вектор, подлежащий исключению из базиса?