6. Пусть у - исходная сумма денег, x.j - сумма, взятая в ночь j, j = 1, 2, 3, х4 - конечная сумма, полученная каждым моряком. Задача ЦЛП:
минимизировать z = у при ограничениях
Зх, - у = 2, х, + Зх2 - у = 2, х, + х2 + Зх3 - у = 2, у - х, - х2 - х3 - Зх4 = 1.
Все переменные неотрицательные целые.
Решение: у = 79 + 81л, п = 0, 1, 2.....
8. На первой стороне кассеты записываются песни 5, 6 и 8, на второй - 1, 2, 3, 4 и 7. Емкость кассеты должна быть не менее 28 минут на каждой стороне. Задача имеет и другие решения.
УПРАЖНЕНИЯ 9.1.2
1. Пусть х - количество продукции, произведенной на станке j = 1, 2, 3; yt = 1, если станок j используется, и yi = 0 в противном случае. Задача ЦЛП:
минимизировать z = 2х, + 10х2 + 5х3 + ЗООу, + 100j/2 + 200i/3
при ограничениях
х, + х2 + х3 > 2000, х, - 600i/, < 0, х2 - 800у2 < 0, х3 - 1200i/3 < 0,
х,, х2, х3 > 500 и целые, </,, у2, у3 = 0 или 1.
Решение: х, = 600, х2 = 500, х3 = 900, z = 11 300 долл.
2. Решение: на участке 1 следует бурить скважины 1 и 2, на участке 2 - скважины 3 и 4, z = 18.
УПРАЖНЕНИЯ 9.1.3
1. Пусть переменные х равны 1, если выбран маршрут у, и равны 0 в противном случае. Задача ЦЛП:
минимизировать z = 80х, + 50х2 + 70х3 + 52х4 + 60х5 + 44х6
при ограничениях
х, + х3 + х5 + х6 > 1, х, + х3 + х4 + х5 > 1, х, + х2 + х4 + х6 > 1,
х, + х2 + х5 > 1, х2 + х3 + х4 + х6 > 1, xt = 0 или 1 для всех у.
Решение: х5 = х6 = 1. Следует выбрать маршруты (1, 4, 2) и (1, 3, 5), z = 104.
2. Решение: в комитет должны войти кандидатуры a, d, f. Задача имеет и другие решения.
УПРАЖНЕНИЯ 9.1.4
1. а) Задача имеет несколько решений, среди которых следующие.
6 4 5
4 5 6
5 6 4
3. Производство следует организовать во втором цехе, при этом продукции 1 следует производить 26 единиц, продукции 2 - 3 единицы, продукции 3 - 0.
УПРАЖНЕНИЯ 9.2.1
1. а) г = 23, дс, = 3, ж2 = 2.
е) г = 37, ж, = 6, х2 = 1. 1. а) г = 7,25, х, = 1,75, х2= 1.
е) 2 = 37, (ж, = 4,6, ж2 = 2) или (xt = 6, ж2 = 1).
УПРАЖНЕНИЯ 9.2.2
1. а) 9 подзадач.
Ь) 25,739 подзадач.
3. Задача ЦЛП с двоичными переменными:
максимизировать г = 18</n + 36</12 + 14</21 + 28у22 + 8у31 + 16i/32 + 32t/33 при ограничении 15j,n + 30j,12 + 12у21 + 24у22 + 7у31 + Ыу32 + 28у33 < 43.
Все переменные двоичные. Решение: z = 50, у1г = 1, y2i = 1, остальные переменные равны 0.
УПРАЖНЕНИЯ 9.2.3
1. а) Да, поскольку это отсечение проходит через целочисленные точки (допустимые и недопустимые) и при этом не исключает ни одной допустимой целочисленной точки.
6. Ь) Оптимальное целочисленное решение: (ж,, ж2, ж3) = (5, 2, 3), 2 = 23.
Решение, полученное путем округления соответствующего оптимального непрерывного решения: (*,, ж2, ж3) = (5, 3, 3). Это решение недопустимо.
УПРАЖНЕНИЯ 9.3.1
1. Количество сотрудников, входящих в комнату для совещаний и выходящих из нее, а также работающих над соответствующими проектами, показано в следующей таблице.
Проект
ГЛАВА 10
УПРАЖНЕНИЯ 10.1
1. Маршрут 1-3-5-7, длина маршрута 21 миля.
УПРАЖНЕНИЯ 10.2
3. Маршрут 1-2-3-5-7, длина маршрута 17 миль.
УПРАЖНЕНИЯ 10.3.1
2. а) Решение: прибыль равна 120, (иг,, т2, т3) = (0, 0, 3) или (0, 2, 2) или
(0, 4, 1)или(0, 6, 0).
4. Решение: общая сумма баллов 250. Выбор курсов: на факультете I курс 2, на факультете II курс 3, на факультете III курс 4, на факультете IV курс 1.
6. Пусть х. = 1, если принимается заявка у, и лс. = 0 в противном случае. Задача о загрузке:
максимизировать г - 78х, + 64х2 + 68х3 + 62х4 + 85х5 при ограничении
7х, + 4х2 + + 5х4 + 8х5 < 23, xt = 0 или 1 для всех j. Решение: принять все заявки, кроме первой. Общая оценка = 279.
УПРАЖНЕНИЯ 10.3.2
1. а) Решение: на 1-й неделе принять 6 человек, на 2-й неделе уволить 1 чело-
века, на 3-й неделе уволить 2 человека, на 4-й неделе принять 3 человека, на 5-й неделе принять 2 человека.
3. На каждую из четырех недель следует арендовать 7, 4, 8 и 8 автомобилей соответственно.
УПРАЖНЕНИЯ 10.3.3
2. а) С-> С->3-> С, затраты = 458 долл.
УПРАЖНЕНИЯ 10.3.4
1. Первый год: инвестировать 5000 долл. в первый банк. Второй год: инвестировать 4090 долл. во второй банк. Третий год: 3090 долл. в первый банк. Четвертый год: инвестировать 2065 долл. в любой банк.
ГЛАВА 11
УПРАЖНЕНИЯ 11.2.1
2. а) Суммарные затраты в неделю составляют 51,50 долл.
Ь) Оптимальная стратегия: заказывать 239,05 фунта фарша, как только его запас опустится до нулевого уровня. Суммарные затраты в неделю составят 50,20 долл.
1. а) Необходимо сделать заказ на 200 единиц продукции в том случае, когда уровень запаса опустится до 150 единиц.
Ь) Приблизительно 91 заказов.