2*, + *2 - 2*3 + s2 - s2 = О,

-0,1*,-од*2 + о,9*3+- s~3 =0>

0,125*,-0,05*2- 0,556*3 + sA - st = 0, -0.2*,+0,8*2-0,2*з+ *s s~s =°. все переменные неотрицательны.

5. Обозначим через х. количество партий изделий, изготовленных в у-ю смену, j = 1, 2, 3. Получаем задачу:

минимизировать s* + s~ при ограничениях -100*, + 40*2 - 80*з + *Г - s; =0, 4<хг< 5, 10 < *2 < 20, 3 < *3 < 5.

УПРАЖНЕНИЯ 8.2.1

1. Целевая функция: минимизировать z = s{ + s2 + + s~ + .

Решение: хн = 0,0201, хр = 0,0457, хо = 0,0582, * = 2 цента, .sj = 1,45, все остальные s, равны нулю. Сумма налога на бензин составляет 1,45 млн. долл. вместо желаемых 1,6 млн.

4. Пусть *, - количество известняка (фунты), потребляемого в день для приготовления кормовой смеси, *2 - количество зерна (фунты), потребляемого в день, *3 - количество соевой муки (фунты), потребляемого в день.

Целевая функция: минимизировать z = sx +s2 +s3+ +sl .

Решение: *, = 166,08, *2 = 2778,56, *3 = 3055,36, 2 = 0. Все цели удовлетворяются.

7. Для производства 80 единиц первого изделия и 60 единиц второго необходимо использование сверхурочных работ: 100 минут для первой операции и 120 минут - для второй.

УПРАЖНЕНИЯ 8.2.2

2. Оптимизация целевой функции G, дает * = 0,0204, х = 0,0457, хо = 0,0582, * = 2, другие переменные равны 0. Цели G G2, G3 и G4 удовлетворяются, цель Gs - нет. Оптимизация целевой функции Gb дает такое же решение, что и оптимизация целевой функции плюс =1,45 . Это указывает на то, что цель Gb удовлетворить невозможно.

ГЛАВА 9

УПРАЖНЕНИЯ 9.1.1

3. Обозначим через лс. количество бутылок типа i, полученных индивидуумом при этом i = 1 (полная бутылка), 2 (заполненная наполовину), 3 (пустая), ; = 1, 2,3. Возможное решение: * = 3, *21 = 1, *3, = 3, *12 = 3, *22 = 1, *32 = 3, *13 = 1, *23 = 5, *33 = 1. Задача имеет и другие решения.

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 миля.