Комплексные задачи

этапе путешествия) с учетом того, что длительность путешествия не может превышать 15 дней. В следующей таблице приведена стоимость проезда на автомобиле и перелета на самолете.

Стоимость полета в Стоимость проезда в

6.2. Некто желает подарить большое количество ценных книг публичной библиотеке. Все книги имеют различные размеры по высоте корешка: 12, 10, 8 и 6 дюймов. Заведующий библиотекой подсчитал, что для размещения книг высотой 12 дюймов необходимы полки общей длиной 12 футов, для книг высотой 10 дюймов - полки длиной 18 футов, для книг высотой 8 дюймов - полки длиной 9 футов и для книг высотой 6 дюймов - полки длиной 10 футов. Цена книжных полок состоит из фиксированной цены и цены, рассчитываемой в зависимости от суммарной длины полок, как показано в следующей таблице.

Высота полки (дюймы) Фиксированная цена (долл.) Цена (долл.) за фут длины полки

12 25 5,50

10 25 4,50

8 22 3,50

6 22 2,50

Сколько и каких полок необходимо для библиотеки, если учесть, что книги меньшего размера могут храниться на полках для книг большего размера?

6.3. Судоходной компании необходимо доставить пять партий груза из портов А, В и С в порты D и Е. Сроки доставки грузов приведены в следующей таблице.

В следующей таблице приведено время перехода (дни) между портами (обратный переход, как правило, требует меньше времени).

Основано на материалах статьи Ravindran A. On Compact Storage in Libraries , Opsearch, Vol. 8, No. 3, pp. 245-252, 1971.

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

6.9. 9 Несколько человек решили основать брокерскую фирму для игры на бирже с ценными бумаги. Брокеры работали по свободной финансовой системе, что позволяло им проводить многочисленные сделки между самими брокерами, включая покупку и продажу ценных бумаг, предоставление денежных ссуд и займов под проценты. Для всей этой группы брокеров, в целом, основным источником доходов были комиссионные, получаемые от продажи ценных бумаг сторонним клиентам.

Со временем эти спекулятивные сделки вышли из-под контроля, что привело всех брокеров к банкротству. К тому же, финансовое положение брокерской фирмы было таково, что все деньги брокеров были вложены во внешних клиентов и сделки между самими брокерами, причем таким образом, что практически каждый брокер стал должником другого.

Брокеры, чьи активы позволяли погасить долги, были объявлены платежеспособными. Остальные через судебные инстанции должны были погасить свои долги в интересах сторонних клиентов. Поскольку активы и авуары несостоятельных брокеров меньше общего объема долгов, долги погашаются пропорционально их объемам.

Из-за финансовых затруднений неплатежеспособной группы брокеров судебные инстанции постановили, что заключенные ранее сделки должны выполняться только для удовлетворения определенных судом требований, поскольку брокеры не имеют собственных источников капитала. В частности, судебные инстанции требуют свести количество погашаемых сделок между брокерами к минимуму. Это означает, что если брокер А должен брокеру В сумму X, а брокер В - брокеру А сумму Y, то эти взаимные долги сведутся к одному с суммой долга Х - Y. Эта сумма считается долгом А перед В, если X > Y, и долгом В перед А, когда X < Y. Если X = У, долг погашен. Эта идея погашения взаимных долгов распространяется на все долги между брокерами.

Каковы ваши предложения по выходу из данной финансовой ситуации? В частности, ответьте на следующие вопросы.

1. Как рассчитать доли возвращаемых долгов?

2. К какому минимальному количеству можно свести взаимные долги между брокерами?

Задача основана на материалах статьи Taha Н. Operations Research Analysis of a Stock Market Problem , Computers and Operations Research, Vol. 18, No. 7, pp.597-602, 1991.

ГЛАВА 7

ТЕОРИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Эта глава представляет строгий математический фундамент теории линейного программирования (ЛП). Здесь будет обоснован симплекс-метод и теория двойственности. Кроме того, будут рассмотрены такие эффективные вычислительные алгоритмы, как модифицированный симплекс-метод, метод декомпозиции, метод решения задач, содержащих ограничения на значения переменных, и методы параметрического программирования. В заключение будет представлен алгоритм Кармаркара, полностью отличный от симплекс-метода. Этот алгоритм наиболее эффективен при решении очень больших задач ЛП.

В этой главе используется аппарат матричной алгебры. Читатель, не знакомый с матричной алгеброй, может обратиться к приложению А.

В задачах линейного программирования пространство допустимых решений всегда имеет форму выпуклого множества. Множество называется выпуклым, если отрезок прямой, соединяющий две различные точки этого множества, полностью принадлежит данному множеству. Крайней точкой выпуклого множества является точка, принадлежащая этому множеству, но которая не лежит ни на каком отрезке прямой, соединяющей две различные точки этого множества. Фактически крайние точки - это то же самое, что и угловые точки, которые использовались в главах 2, 3 и 4.

На рис. 7.1 показаны два множества. Множество а, которое представляет типичное пространство решений задачи ЛП, является выпуклым множеством, тогда как множество б невыпуклое.

7.1. ОСНОВЫ СИМПЛЕКС-МЕТОДА

Рис. 7.1. Примеры выпуклого и невыпуклого множеств