назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


71

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

iii) Если новое распределение нулевых элементов не позволяет построить допустимое решение, повторите этап 2.1. В противном случае перейдите к третьему этапу алгоритма.

В задаче данного примера выполнение этапа 2.1 требует проведения трех прямых и приводит к табл. 5.38.

Таблица 5.38

Виды работ 3

Дети

Наименьший невычеркнутый элемент (он подчеркнут) равен 1. Этот элемент вычитаем из остальных невычеркнутых элементов и прибавляем к элементам, стоящим на пересечении прямых. В результате получим матрицу, представленную в виде табл. 5.39.

Таблица 5.39

Виды работ

Дети 2

Оптимальное решение, показанное в таблице подчеркнутыми нулями, предлагает первому ребенку работу 1, второму - работу 3, третьему - работу 2 и четвертому - работу 4. Соответствующее значение целевой функции равно 1 + 10+ 5+ 5 = 21 долл. Такое же значение можно получить путем суммирования значений pt и q. и значения элемента, наименьшего среди всех невычеркнутых: (1 + 7 + 4 + 5) + (0 + 0 + 3 + 0) + (1) = 21 долл.

УПРАЖНЕНИЯ 5.4

1. Решите задачи о назначениях, представленные в табл. 5.40.

Таблица 5.40



a) Решите задачи венгерским методом.

b) С помощью программы TORA решите задачи как транспортные.

c) Запишите задачи как задачи ЛП и решите их с помощью программы TORA.

d) Решите задачи в Excel с помощью шаблона ch5SolverTransportation.xls.

e) Решите задачи с помощью программы LINGO.

2. Дана следующая задача распределения четырех рабочих по четырем видам работ. Различная квалификация рабочих обусловливает различную стоимость выполнения работ. Стоимость работ (долл.) приведена в табл. 5.41. Отметим, что первый рабочий не может выполнять работу 3, а третий - работу 4. Найдите оптимальное решение.

Таблица 5.41

Виды работ

Рабочие 2

3. Пусть в задаче из предыдущего упражнения можно ввести нового (пятого) рабочего, способного выполнить любой вид работ со стоимостью соответственно 60, 45, 30 и 80 долл. Будет ли экономически выгодным заменить одного из "работающих" рабочих новым?

4. Пусть в задаче из упражнения 2 необходимо ввести новый вид работы, который может выполнить любой из четырех рабочих, со стоимостью соответственно 20, 10, 20 и 80 долл. Будет ли новая работа более выгодной по сравнению с имеющимися?

5. Бизнесмен должен сделать четыре поездки туда и обратно из своего головного офиса в Далласе в филиал в Атланте (данные о поездках приведены в табл. 5.42). Билет туда и обратно, т.е. Даллас-Атланта-Даллас, стоит 400 долл. Скидка 25% предоставляется тогда, когда даты отправления и прибытия совпадают с выходными днями (суббота и воскресенье). Если в билете между датами прибытия в Атланту и отправления из нее не менее 21 дня, то скидка увеличивается до 30%. Билет в одну сторону (в любом направлении) стоит 250 долл. Какую минимальную сумму может потратить на билеты бизнесмен?

Таблица 5.42

Дата отправления из Далласа Дата возвращения в Даллас Понедельник, 3 июня Пятница, 7 июня

Понедельник, 10 июня Среда, 12 июня

Понедельник, 17 июня Пятница, 21 июня

Вторник, 25 июня Пятница, 28 июня

6. На рис. 5.8 схематически показан план обрабатывающего цеха с четырьмя старыми станками, обозначенными квадратиками с номерами от 1 до 4. В цех будут



поставлены четыре новых станка, местоположение которых обозначено кружочками с буквами а, Ь, с и d. Необходимо так разместить новые станки, чтобы минимизировать суммарные перемещения обрабатываемых деталей между новыми и старыми станками. В табл. 5.43 показана интенсивность перемещения деталей между новыми и старыми станками. Детали перемещаются по сторонам прямоугольника, противоположными вершинами которого будут старый и новый станки. Например, расстояние (в метрах) между станком 1 и станком, расположенным в позиции Ь, равно 30 + 20 = 50 м.

О 10 20 30 40 50 60 70 80 Рис. 5.8. Расположение станков в задаче упражнения 6

Таблица 5.43

Старые станки

Новые станки 2 3

5.4.2. Интерпретация венгерского метода как симплекс-метода

Задачу о назначении п работников на п видов работ можно представить в виде задачи линейного программирования следующим образом. Обозначим через с(/ стоимость назначения работника i на работу у и определим

1, если работник / назначен на работу у, 0, в противном случае.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [ 71 ] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]