Материал: 3823
15
Как закрепить датчики за регистрирующими устройствами, чтобы суммарные затраты времени были минимальными?
Вариант 10
В резерве трех железнодорожных станций a1 , a2 , a3 находятся соответственно 60, 80, 70 вагонов. Составить оптимальный по стоимости план перегона этих вагонов к четырем пунктам погрузки зерна, если пункту b1
требуется 40, пункту b2 – 60, пункту b3 – 50, пункту b4 – 60 вагонов.
Стоимость перегона одного вагона со станции a1 в указанные пункты соответственно равна 220, 240, 300 и 280 рублям; со станции a2 – 280, 260, 240
и 220 рублям; со станции a3 – 300, 240, 280 и 320 рублям.
Вариант 11
Три фабрики a1 , a2 , a3 снабжают четыре магазина b1 , b2 , b3 , b4 холодильниками. Первому магазину требуется 10 холодильников, второму – 8, третьему – 8 и четвертому – 11 холодильников. На первой фабрике изготовили 11 холодильников, на второй – 14, на третьей – 12. Стоимость перевозки (в рублях) одного холодильника в магазин задается таблицей:
bj |
|
|
|
|
|
|
b1 |
|
b2 |
b3 |
b4 |
ai |
|
|
|
|
|
|
|
|
|
|
|
a1 |
|
240 |
180 |
270 |
210 |
|
|
|
|
|
|
a2 |
|
180 |
150 |
210 |
180 |
a3 |
|
240 |
180 |
210 |
240 |
Выяснить, сколько холодильников нужно отправить с каждой фабрики в каждый магазин, чтобы общая стоимость перевозок при этом была минимальной.
Вариант 12
Необходимо провести испытания большой партии оборудования для самолетов на пяти базах b1 , b2 , b3 , b4 , b5 . Оборудование находится на складах
16
в трех городах a1 , a2 , a3 . Это оборудование по воздуху доставляется в пункты назначения. В таблице заданы расстояния в километрах, количество имеющихся и количество требуемых комплектов оборудования. Требуется минимизировать количество тонно-километров при перевозке оборудования.
bj |
|
|
|
|
|
|
Количество |
|
b1 |
|
b2 |
b3 |
b4 |
b5 |
имеющихся |
ai |
|
|
|
|
|
|
комплектов |
|
|
|
|
|
|
|
|
a1 |
|
940 |
1000 |
820 |
140 |
1000 |
8 |
|
|
|
|
|
|
|
|
a2 |
|
350 |
1800 |
1400 |
800 |
300 |
5 |
|
|
|
|
|
|
|
|
a3 |
|
900 |
1600 |
1600 |
960 |
860 |
8 |
|
|
|
|
|
|
|
|
Требуемое |
|
|
|
|
|
|
|
количество |
3 |
|
5 |
5 |
5 |
3 |
|
комплектов |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вариант 13
Зерно из четырех районов a1 , a2 , a3 , a4 должно быть перевезено на три
элеватора b1 , |
b2 , b3 . Ожидаемый |
сбор |
зерна в |
районах: a1 400 тыс. ц, |
||||||
a2 500 тыс. ц, |
|
a3 800 тыс. ц и |
a4 500 тыс. ц. |
Мощности элеваторов: |
||||||
b1 700 тыс. ц, |
b2 800 |
тыс. ц и b3 700 тыс. ц. Затраты на перевозку одного |
||||||||
центнера зерна (в рублях) из районов к элеваторам приведены в таблице: |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bj |
|
|
|
|
|
|
|
|
|
|
|
b1 |
|
|
b2 |
|
b3 |
|
|
|
ai |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a1 |
|
|
10 |
|
40 |
|
30 |
|
|
|
a2 |
|
|
70 |
|
10 |
|
50 |
|
|
|
a3 |
|
|
40 |
|
80 |
|
30 |
|
|
|
a4 |
|
|
40 |
|
20 |
|
80 |
|
|
|
|
|
|
|
|
|
|
|
|
17
Определить план перевозок с минимальными транспортными затратами.
Вариант 14
Имеются три специализированные мастерские «Сельхозтехники» по ремонту двигателей b1 , b2 , b3 . Их производственные мощности равны соответственно 230, 190, 210 ремонтов в год. В четырех районах a1 , a2 , a3 , a4 , обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 180, 150, 120 и 180 двигателей в год. Затраты (в рублях) на перевозку одного двигателя из районов в мастерские приведены в таблице:
bj |
|
|
|
|
|
|
b1 |
|
b2 |
|
b3 |
ai |
|
|
|
|
|
a1 |
|
90 |
|
54 |
174 |
|
|
|
|
|
|
a2 |
|
42 |
|
86 |
48 |
|
|
|
|
|
|
a3 |
|
150 |
|
62 |
84 |
|
|
|
|
|
|
a4 |
|
106 |
|
38 |
124 |
Определить план прикрепления районов к мастерским, обеспечивающий минимальные транспортные расходы.
Вариант 15
На вокзалы a1 и a2 прибыло по 30 комплектов мебели. Известно, что перевозка одного комплекта с вокзала a1 в магазины b1 , b2 , b3 стоит 60 рублей, 150 рублей, 120 рублей соответственно, а с вокзала a2 в те же магазины – 30 рублей, 90 рублей и 150 рублей соответственно. Необходимо доставить по 20 комплектов в каждый магазин. Составить план перевозок с минимальной общей стоимостью.
18
Образец выполнения РГР.
Задание № 1. Решить задачу линейного программирования графическим методом
В процессе производства двух видов изделий А и В эти изделия должны пройти обработку на станках I, II, III, IV. Время обработки каждого изделия на каждом из станков приведено в таблице:
Виды изделий |
|
Станки |
|
||
|
|
|
|
||
I |
II |
III |
IV |
||
|
|||||
|
|
|
|
|
|
А |
2 |
0 |
8 |
5 |
|
|
|
|
|
|
|
В |
0 |
2 |
5 |
5 |
|
|
|
|
|
|
|
Станки можно использовать соответственно в течение 90, 80, 390 и 300 часов. Прибыль от реализации одного изделия вида А составляет 60 рублей, а от реализации одного изделия вида В – 20 рублей. Составить план производства изделий видов А и В, дающий наибольшую прибыль.
Решение. |
Пусть |
x1 |
– количество изделий вида А, планируемое |
к |
|||
производству, |
x2 |
– количество изделий вида В, планируемое к производству. |
|||||
Тогда прибыль |
от |
реализации произведенной продукции |
составит |
||||
F 60x1 20x2 |
рублей. Согласно условию задачи, на переменные |
x1 и |
x2 |
||||
налагаются следующие ограничения: |
|
|
|
||||
|
|
|
|
2x1 90, |
|
|
|
|
|
|
|
2x2 80, |
|
|
|
|
|
|
|
8x1 5x2 |
390, |
|
|
|
|
|
|
5x1 5x2 |
300. |
|
|
Кроме этого, переменные x1 |
и x2 должны иметь неотрицательные значения. |
|
|||||
Получаем стандартную задачу линейного программирования с двумя переменными: найти максимум линейной функции
F 60x1 20x2
для переменных x1 , x2 , удовлетворяющих системе ограничений-неравенств
19
2x1 90,2x2 80,
8x1 5x2 390,5x1 5x2 300
и условиям неотрицательности x1 0 , x2 0.
Решим эту задачу графическим методом. Для каждого из неравенств системы строим прямую с соответствующим уравнением и определяем полуплоскость, точки которой имеют координаты, удовлетворяющие данному неравенству. Пересечение всех этих полуплоскостей и первого координатного угла является областью допустимых решений системы неравенств (многоугольник ODEGHK на рис.1). Затем в этой же системе координат строим вектор c 60, 20 . Перпендикулярно вектору c строим линию уровня с
уравнением 60x1 20x2 0 и перемещаем еѐ в направлении вектора c
параллельно еѐ начальному положению. Вектор c показывает направление роста значений функции F . Видим, что опорная прямая проходит через точку H (см. рис. 1), поэтому в точке H функция F принимает максимальное значение (в области допустимых решений).
Рис. 1.