«Brian D Bunday, B.Sc., Ph.D., F.S.S., F.I.M.A. School of Mathematical Sciences, University of Bradford Edward Arnold Б. Банди ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Перевод с английского О.В. Шихеевой Под редакцией В.А. ...»

Для нее требуются 2 м3 воды на 1 акр и весьма большие затраты труда — 4 человека на акров. В текущих единицах на мировом рынке она принесла бы б единиц чистого урожая с акра. Стоит ли ее выращивать? 9. Компания импортирует красные вина трех марок:

Красные вина смешиваются для получения столовых вин трех марок:

Нюи-Сент-Жорж 30 (бургундское) 30 (испанское красное) Не ограниченно 2, Сформулируйте задачу как задачу линейного программирования и решите ее улучшенным симплекс-методом. Считайте, что прибыль - единственное, что интересует компанию.

10. На k-й итерации в решении задачи линейного программирования с использованием улучшенного симплекс-метода одна базисная переменная хр обратилась в 0. Она дает неопределенность вместе с переменной хr предназначенной для исключения из базиса на предыдущей итерации. Покажите, что это базисное допустимое решение не может снова встретиться при прохождении циклов.

11. Используйте улучшенный симплекс-метод для решения некоторых транспортных задач гл. 4. Как он связан со специализированной программой для этих эадач?

12. Используйте улучшенный симплекс-метод для решения нескольких задач выбора гл. 5.

Как он связан с программой, основанной на методе Мака?

ГЛАВА 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ

ПРОГРАММИРОВАНИИ

7.1. ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ Многие из полученных результатов легче объяснить, введя понятие двойственности. Мы увидим, что каждой задаче линейного программирования соответствует другая (двойственная) задача. Если понять взаимосвязь между этими задачами, то можно получить решение обеих, когда известно решение любой их них. Введем новые понятия.

Прямая задача:

найти такие x j 0 ( j = 1, 2, K, n ), что Ей соответствует двойственная задача:

найти такие y i 0 i = 1, 2, K, m, что На самом деле нам уже встречались прямая и двойственная задачи в упр. 5, 6 гл. 2 и в упр.

3, 4 гл. 6.

Исходная задача:

и функция 50 x1 + 25 x 2 = z имеет минимальное значение.

Соответствующая двойственная задача:

и функция 8 y1 + 19 y 2 + 7 y3 = w имеет максимальное значение.

Прямая задача имеет ограничения в виде неравенства со знаком, а двойственная - со знаком. Количество переменных в прямой задаче совпадает с количеством переменных в двойственной задаче. Матрица коэффициентов ограничений двойственной задачи является транспонированной матрицей коэффициентов прямой задачи. Коэффициенты целевой функции двойственной задачи являются значениями правых частей ограничений прямой задачи, и наоборот.

В матричной записи прямая задача имеет следующий вид:

найти такой x 0, что и функция имеет минимальное значение.

Двойственная задача в матричном виде записывается следующим образом:

найти такой y 0, что имеет максимальное значение.

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

Пример Привести к стандартной форме прямую задачу и функция x1 4 x 2 3 x3 = z имеет максимальное значение.

Сформулировать двойственную задачу.

Максимизация функции z равносильна минимизации, например, функции z = z.

Ограничение x3 4 умножением на -1 преобразуется в ограничение x3 4.

Ограничение равносильно двум ограничениям Таким образом, задача может быть переписана следующим-образом:

и функция x1 + 4 x 2 + 3 x3 = z имеет минимальное значение.

Это - стандартная форма прямой задачи.

Двойственная задача имеет следующий вид:

(смысл этих обозначений скоро станет ясен), что и функция 7 y1 + 6 y 6 y 4 y3 = w имеет максимальное значение.

Это стандартная двойственная задача. Видно, что y 2 = y y может считаться единственной переменной из-за вида коэффициентов (вот в чем смысл обозначений), и задача может быть переписана так:

найти такие y1 0, y 2 (знак y 2 неопределен), y3 0, что и функция 7 y Пример Найти двойственную задачу для задачи найти такие x1 0 и x 2 неопределенного знака, что и функция 6 x1 + 10 x 2 имеет минимальное значение.

Если мы выразим x 2 через x x, где x и x 0, задача примет стандартную форму для прямой задачи:

Соответствующая двойственная задача имеет вид и функция 10 y1 4 y 2 имеет максимальное значение.

Двойственная задача приведена в стандартной форме. Однако два последних ограничения равносильны, так что двойственная задача может быть представлена в следующем виде:

и функция 10 y1 4 y 2 = w имеет максимальное значение.

Таким образом, из примеров настоящего раздела видно, что каждому ограничению прямой задачи соответствует переменная двойственной задачи, а каждой переменной прямой задачи соответствует ограничение двойственной задачи. Если ограничение в прямой задаче задано в виде равенства, то соответствующая переменная двойственной задачи не ограничена знаком (пример 1); если переменная прямой задачи не ограничена знаком, соответствующее двойственное ограничение является равенством (пример 2).

7.2. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ Теорема 1. Двойственная задача к двойственной есть прямая задача.

С помощью уравнений (7.4) двойственная задача может быть записана (исходя из прямой в стандартной форме) следующим образом: найти такой y = 0, что и функция b T y = w имеет минимальное значение. Ее двойственная задача имеет вид найти такой x 0, что и функция c T x = z имеет максимальное значение.

Но она равносильна задаче найти такой x 0, что и функция c T x = z имеет минимальное значение, а это и есть прямая задача.

Теорема 2. Значение функции z, соответствующее любому допустимому решению прямой задачи, не меньше значения функции w, соответствующего допустимому решению двойственной задачи.

Пусть X и Y - допустимые решения соответственно прямого и двойственного ограничения. Пусть соответствующие значения целевой функции Из уравнения (7.3) AX b.

Поскольку Y 0, то Далее из уравнения (7.4) AT Y Однако X T AT Y - скалярная величина, поэтому равна своей транспозиции Y T AX, следовательно, Из этого результата следует, что если имеется допустимое значение функции z, равное допустимому значению функции w, то это должно быть минимальное значение функции z и максимальное значение функции w. Ниоткуда не следует, что такие значения существуют.

Теорема 3. Если прямая задача имеет конечное решение z = z min, то двойственная задача имеет конечное решение w = w max = z min. При этом симплекс-множители оптимального решения прямой задачи являются значениями переменных в оптимальном решении двойственной задачи, взятыми с противоположным знаком.

Если в ограничения прямой задачи вводятся новые переменные, прямая задача принимает вид и функция c1 x1 + c 2 x 2 + K + c n x n = z имеет минимальное значение.

Если 1, 2, K, m - симплекс-множители оптимального решения, то после умножения ограничений на 1, 2, K, m и прибавления к выражению для функции z получаем уравнение Далее если уравнение (7.6) - оптимальная каноническая форма для функции z, то все коэффициенты левой части неотрицательны. Следовательно, Эти ограничения равносильны ограничениям так что значения i удовлетворяют свойственным ограничениям.

Разумеется, в уравнении (7.6) коэффициенты при базисных переменных обратятся в 0;

сами базисные переменные также равны 0, так что левая часть равна 0 и допустимому решению ограничений двойственной задачи, задаваемому равенствами Таким образом, в силу замечаний после уравнения (7.5) эта величина является максимальным значением функции w. Следовательно, Теорема 4. Если двойственная задача имеет конечное решение w = w max, то прямая задача имеет конечное решение z min = w max. Значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи.

Это может быть выведено из теорем 1 и 2; но полезно также получить прямое доказательство в матричных обозначениях, аналогичное доказательству теоремы 3.

Двойственная задача с ограничениями в виде равенства может быть записана как максимизировать функцию bT y = w при ограничениях AT y + y s = c, - вектор новых переменных.

двойственной задачи, то следовательно Далее, поскольку функция w максимизируется (а не минимизируется, как обычно), коэффициенты при y и y s в левой части уравнения (7.11) не должны быть положительными, следовательно, что можно записать в виде Так что значения удовлетворяют ограничениям прямой задачи. То же рассуждение показывает, что Следствием теорем 3 и 4 является то, что при встрече с задачей линейного программирования мы вольны выбирать, решать ли задачу в том виде, как она поставлена, или решать двойственную задачу. Если применяется улучшенный симплекс-метод (что настоятельно рекомендуется), то будут получены и значения переменных, и симплексмножители. Это позволит определить также симплекс-множители и значения переменных другой задачи. Таким образом можно сильно сэкономить время вычислений. Как было указано в разд. 6.4, объем вычислений в задаче линейного программирования связан скорее с количеством ограничений, чем с количеством переменных.

Значит, если в прямую задачу входят 7 ограничений на 3 переменные, преобразования будут производиться в матрице размерностью 9 X 8 на этапе I и в матрице размерностью 8 X 8 на этапе II. В двойственную задачу входят 3 ограничения на 7 переменных, и она независима от этапа I; преобразования будут производиться в матрице размерностью 4X4.

Таким образом, из каждой итерации объем вычислений сокращается по меньшей мере в четыре раза.

В качестве иллюстраций к теоремам 3 и 4 рассмотрим задачу и функция 7 x1 + 10 x 2 = z имеет минимальное значение.

Ее двойственная задача имеет вид и функция 10 y1 + 19 y 2 + 9 y3 = w имеет максимальное значение.

Решение первой задачи на ЭВМ показывает, что в оптимальном решении x1 = 1, образом, для другой задачи решением является y1 = 0, y 2 = 2, y 2 = 3, где Это подтверждается решением двойственной задачи на ЭВМ. Здесь требуется некоторое внимание. При решении на ЭВМ, используя линейное программирование, мы минимизировали функцию (знаки целевой функции и симплекс-множителей здесь обращены).

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

МОДИФИЦИРОВАННЬМ СИМПЛЕКС-МЕТОДОМ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

ПЕРВЫЙ ЗТАП ВСЕ ЕЩЕ ПРОДОЛЖАЕТСЯ

X 2 ВХОДИТ В,Х 6 В УСЛОВИИ 1 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ 0.00 0.00 0.00 0.00 10. РЕШЕНИЕ ДЛЯ ИСКУССТ.ФУНКЦИИ -38.00 -1.00 -1.00 -1.00 -9.

ПЕРВЫЙ ЭТАП ВСЕ ЕЩЕ ПРОДОЛЖАЕТСЯ

X 3 ВХОДИТ В,Х 8 В УСЛОВИИ 3 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

ПЕРВЫЙ ЗТАП ВСЕ ЕЩЕ ПРОДОЛЖАЕТСЯ

X 5 ВХОДИТ В,Х 7 В УСЛОВИИ 2 ВЬВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ -45.00 0.00 0.00 -5.00 5. РЕШЕНИЕ ДЛЯ ИСКУССТ.ФУНКЦИИ -1.00 0.00 -1.00 2.00 -2.

ЗТАП 1 УСПЕШНО ЗАВЕРЕН

-0.50 0.00 0.00 2.50 0.

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ -47.50 0.00 -2.50 0.00 -0.

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

МИНИМУМ ФУНКЦИИ Z РАВЕН

ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЫЕ

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ -47.00 0.00 -2.00 -1.

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

МОДИФИЦИРОВАННЫМ СИМПЛЕКС-МЕТОДОМ

ОТСУТСТВУЕТ ЭТАП 1 РЕШЕНИЯ ЗАДАЧИ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

2 10.00 3.00 4.00 2.00 0.00 1. ЦЕЛЕВАЯ ФУНКЦИЯ -10.00 -19.00 -9.00 0.00 0. -10.00 -19.00 -9.00 0.00 0,

X 2 ВХОДИТ В,Х 4 В УСЛОВИИ 1 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ 0.00 0.00 0.00 -19. 2.67 0.00 -2.67 6.33 0.

X 3 ВХОДИТ В,Х 5 В УСЛОВИИ 2 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'IS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ 44.33 6.33 0.00 -2.

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

МИНИМУМ ФУНКЦИИ Z РАВЕН -

ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЫЕ

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА

Уместно еще одно замечание. Из уравнения (7.6) видно, что в оптимальном решении прямой задачи Из уравнения (7.11) видно, что в оптимальном решении двойственной задачи Таким образом, по крайней мере один из i и xn + i равен 0 и по крайней мере один из j и ym + j равен 0. Эти результаты можно сформулировать следующим образом.

Пусть в оптимальном решении прямой задачи k -e ограничение, не связывающее ( xn + k > 0 ), тогда значение k -й двойственной переменной ( k ) равно 0. Если k -я двойственная переменная положительна, то k -e ограничение прямой задачи связывающее.

Эти результаты иногда называют принципом комплементарности дополнительных переменных.

7.3. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ С ТОЧКИ ЗРЕНИЯ

ДВОЙСТВЕННОСТИ

Понятие двойственности помогает лучше осознать некоторые полученные выше результаты линейного программирования.

Алгоритм двойственного симплекс-метода (см. разд. 3.3) был выведен без обращения к двойственности. Однако двойственность позволяет взглянуть на процедуру по-другому.

Рассмотрим задачу и функция 4 x1 + 6 x2 + 18 x3 = z имеет минимальное значение.

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

Таким образом, в оптимальном решении и x Симплекс-множители (коэффициенты при новых переменных x 4 и x5 в окончательном виде для функции z ) равны 1 = 2 и 2 = 6.

Рассмотрим двойственную задачу найти такие y1 0, y2 0, что и функция 3 y1 + 5 y2 = w имеет максимальное значение.

При обычном подходе к задаче мы минимизируем функцию Приведем таблицу последовательных вычислений:

Симплекс-множители (для целевой функции (коэффициенты при новых переменных y3, y4 и y5 ). Они дают значения переменных прямой задачи. Двойственные переменные y1 = 2 и y2 = 6 являются симплексмножителями прямой задачи. В проведенных вычислениях двойственный симплекс-метод для решения прямой задачи и симплекс-метод для решения обратной задачи, по существу, идентичны.

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

Транспортная задача может быть сформулирована в следующем виде:

найти такие xij 0, что и функция c11 x11 + c12 x12 + K + cmn xmn = z принимает минимальные значения (см. уравнение (4.2)).

Для решения двойственной задачи необходимо найти такие ui и v j (знаки которых не определены, поскольку ограничения исходной задачи являются равенствами), что максимальное значение.

Попытаемся выполнить ограничения двойственной задачи ui + v j cij. Это не слишком трудно, поскольку в каждое ограничение входит всего две переменные. На самом деле в m + n 1 клетке (каждая из которых соответствует базисной переменной прямой задачи) достигается равенство в двойственных ограничениях (свойство комплементарности дополнительных переменных). Когда ограничения двойственной задачи выполнены как неравенства, в других клетках получим решения обеих задач.

Дело в том, что умножение в прямой задаче i -и строки и j -го столбца на ui и v j с последующим прибавлением к выражению для функции z дает соотношение (см. уравнение (4.7)).

Выберем ui и v j - так, чтобы ui равенство z = w на каждом шагу.

Когда для небазисных переменных xij cij ограничений двойственной задачи с равными значениями функций z и w. Таким образом, это должно давать оптимальное решение обеих задач.

Читатель может поинтересоваться, что произойдет, если рассмотреть прямую задачу (или, на самом деле, любую задачу линейного программирования) с точки зрения общей теории (теоремы Куна-Такера) оптимизации с ограничениями. Для читателя, незнакомого с этими идеями, изложим начальные понятия теории применительно к нашим задачам.

Рассмотрим задачу минимизировать функцию Обычно d j = 0, но здесь, пренебрегая этим, имеет смысл сформулировать задачу в общем виде. Запишем ограничения (7.18) и (7.19) в виде и определим функцию Лагранжа где i и j - так называемые множители Лагранжа.

Условный минимум, определенный уравнением (7.17), задается безусловным минимумом, определенным уравнением (7.22), необходимые условия которого задаются уравнениями Видно, что уравнения (7.24) и (7.25) равносильны уравнениям (7.18) и (7.19). Уравнения (7.26) и (7.27) отражают свойство комплементарности дополнительных переменных.

Множители Лагранжа i эквивалентны симплекс-множителям.

Значения переменных удовлетворяют ограничениям Далее из уравнения (7.22) получаем уравнения Сравните их с уравнением (3.17).

Теперь при увеличении bi и d j - область ограничений уменьшается, так что Fmin не может уменьшаться, значит, Сравните с уравнениями (7.7). Таким образом, из уравнения (7.23) имеем следовательно, так что значения i удовлетворяют двойственным ограничениям.

Далее для значения Fmin, соответствующего значениям x, и т. д., удовлетворяющим необходимым условиям минимума, в силу уравнений (7.27) при d j Для этих значений т. е. zmin = w max в обозначениях прямой и двойственной задач.

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

7.4. УПРАЖНЕНИЯ 1. Запишите задачу, двойственную задаче найти такие x1 0, x2 0, что и функция 11x1 + 44 x2 имеет минимальное значение.

2. Напишите задачу, двойственную задаче найти такие x1 0, x2 0 и x3, не ограниченный в знаке, что и функция 5 x1 + 7 x2 + 13 x3 имеет минимальное значение.

3. Покажите, что если k -я переменная в прямой задаче не ограничена в знаке, то k -e ограничение в двойственной задаче есть ограничение в виде равенства.

4. Покажите, что если k -e ограничение в прямой задаче есть ограничение в виде равенства, то k -я переменная в двойственной задаче не ограничена в знаке.

и функция 11x1 + 14 x2 + 15 x3 = z имеет минимальное значение.

Решите двойственную задачу и подтвердите правильность теорем 3 и 4 этой главы.

6. Для задачи найти такие x1 0, x2 0, что и функция x1 x2 = z имеет минимальное значение (пример 3 разд. 1.2), выпишите двойственную задачу и покажите, что допустимого решения не существует.

7. Покажите, что если прямая (двойственная) задача имеет неограниченное решение с неограниченным значением z (w ), то двойственная (прямая) задача не имеет допустимого решения.

8. Покажите, что утверждение, обратное сформулированному в упр. 7, неверно.

Постройте контрпример.

9. Проверьте теоремы 3 и 4 для задачи и функция 7 x1 + 4 x2 + 11x3 = z имеет минимальное значение.

10. Пекарня продает быстропортящиеся пироги, которые должны быть проданы в день выпечки. Известны вероятности спроса p0 = 1 8, p1 = 1 8, p2 = 1 4, p3 = 1 2, где p j - вероятность того, что j - дневной спрос. Стоимость выпечки j пирогов в день составляет C j, где C - константа. Покажите, что задача удовлетворения спроса в среднем, по крайней мере в один день из четырех, с минимизацией выпечки является задачей линейного программирования.

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

РЕКОМЕНДАЦИИ ДЛЯ ДАЛЬНЕЙШЕГО ЧТЕНИЯ

Читателей может заинтересовать обращение к оригинальным работам, упоминавшимся в книге. Упоминаются также несколько других монографий, посвященных методам и приложениям линейного программирования.

СПИСОК ЛИТЕРАТУРЫ

1. Beale, E.M.L. Cycling in the Dual Simplex Algorithm, Nav. Res. Logistics Quart., 2, 2. Dantzig, G.B. 'Maximisation of a linear function of variables subject to linear inequalities', in Activity Analysis of Production and Allocation (Edited by Т. С.

Koopmans), Wiley, New o York, 1951.

3. Dantzig, G.B. Linear Programming and Extensions, Princeton University Press, New 4. Dantzig, G.B. 'The Simplex Method', Rand Corp. Rept., P-891, 1956.

5. Dantzig, G.B. and Orchard-Hays, W. 'Alternate Algorithm for the Revised Simplex Method Using Product Form for the Inverse', Rand Corp. Rept., RM-1268,1953.

6. Ford, L.R., Jr. and Fulkerson, D.R. Solving the Transportation Problem, Man. Sc., 3, 24Gale, D. The Theory of Linear Economic Models, McGraw-Hill, New York, 1960.

8. Garvin, W.W. Introduction to Linear Programming, McGraw-Hill, New York, 1960.

9. Gass, S.I. Linear Programming: Methods and Applications, McGraw-Hill, 3rd Ed., New 10. Glover, F., Karney, D., Klingman, D. and Napier, A. A Computation Study on Start Procedures, Basis Change Criteria and Solution Algorithms for Transportation Problems, Man. Sc., 20,793-813, 1974.

11. Hadley, G. Linear Programming, Addison Wesley, Reading, Mass., 1962.

12. Hitchcock, F.L. The Distribution of a Product from Several Sources to Numerous Localities, J. Math. Phys., 20, 224-230, 1941.

13. Hoffman, A.J. Cycling in the Simplex Algorithm, Nat. Bur. Standards Rept., 2974,1953.

14. Kuhn, H.W. The Hungarian Method for the Assignment Problem, Nav. Res. Logistics 15. Mack, C. The Bradford Method for the Assignment Problem, The New J. of Stats, and Op. Res., 1, Part 1, 17-29, 1969.

16. Orchard-Hays, W. Advanced Linear Programming Computing Techniques, McGrawHill, New York, 1968.

17. Wagner, H.M. A Comparison of the Original and Revised Simplex Methods, Op. Res., 5, 18. Walsh, G.R. An Introduction to Linear Programming, Holt, Rinehart and Winston, 1971.

ПРИЛОЖЕНИЕ

Приведенная ниже процедура была разработана доктором Скратоном из университета г.

Брадфорда; она используется для форматирования численных результатов некоторых из программ. Это достигается тем, что числа рассматриваются как строки.

Для использования процедуры проделайте следующие три шага:

1. РА - число, которое должно быть напечатано.

2. РВ - код форматирования (см. ниже).

3. GOSUB 9000.

РВ - двух-трехзначное число, РВ = 100* А + 10* В + С, где А, В, С - цифры от 0 до включительно.

Если А = 0, число печатается на новой строчке. Если А > 0, число печатается на той же строчке, что и предыдущее, после А пробелов. При выводе на печать оно содержит В знаков до десятичной запятой и С знаков после. Знак печатается, если число отрицательно. Если оно слишком велико для форматирующего кода, то печатается обычным образом.

9000 РС=INT(РВ/100) 9020 IF PC=0 THEN PRINT"":GOTO 9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC 9050 PD=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN PD= 9070 IF РA=10^PD THEN PRINT РA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT".";

9150 PE=INT((PE-INT(PE))*10^PC) 9160 P$="000000000" 9170 P$=P$+MID$(STR$(PE),2,PC) 9180 PRINT RIGHT$(P$,PC);:RETURN

ОТВЕТЫ К УПРАЖНЕНИЯМ

1.6. УПРАЖНЕНИЯ Максимизировать функцию z = 5 x1 + 3 x2 при ограничениях Оптимальное решение получено при x1 = 60, x2 = 40, z = 420 дол. в неделю.

2. Максимум функции равен 10 при x1 = 2, x2 = 4.

4. Минимум функции равен -10 при x1 = 4, x2 = 2.

5. а) Минимум функции равен -13 при x1 = 3, x2 = 2.

б) Минимум функции равен -9 при в) Решение не ограничено.

6. Нет решения, так как ограничения противоречивы.

7. Максимум функции равен 12/5 при x1 = 2 / 5, x2 = 1 / 5, x3 = 0.

9. x1, x2, x3 - проценты содержания сортов А, В, С. Минимизировать функцию 70 x1 + 50 x2 + 10 x3 при ограничениях Оптимальное решение найдено при x1 = 17 / 59, x2 = 6 / 59, x3 = 36 / 59.

0 x1 30,0 x2 20,3 x1 + 3 x2 100. Оптимальное решение найдено при 12. Пункт А получает 1, 4, 0 автобусов из гаражей G1, G2, G3 соответственно; пункт В получает 2, 0, 5 автобусов из гаражей G1, G2, G3 соответственно. Покрывается общее расстояние 25 миль.

14. 367 моделей "Каприз", 683 модели "Фиаско".

15. Пусть x т перевозятся из Лидса в Манчестер, y т - из Лидса в Бирмингем.

а) Оптимальное решение достигается при x = 400, y = 400 ;

2.6. УПРАЖНЕНИЯ 3. x A = 13,125, x B = 2,625 прибыль равна 55,125 дол.

4. 40 000 пол-литровых бутылок и 20 000 литровых бутылок выпустить на машине А, 10 000 литровых бутылок - на В.

7. xi - количество радиаторов каждой модели, x A = 400, x B = 0, xC = 150, x D = 0 ; прибыль равна 3875 дол.

8. x A = 2000, x B = 7000 ; прибыль равна 10 350 дол.

10. 200 000 дол. - на телевизоры, 100 000 дол. - на радио, 100000 дол.- на газеты, дол. - на афиши.

12. Минимальная цена - 150 (условных единиц); 5/6кг сушеной рыбы, 5 кг фруктов, 3 л молока.

13. Использовать 9000 галлонов W в А, 81 000 галлонов Y в А, галлонов W в В, 85 000 галлонов Y в В, 24 000 галлонов X в С, галлонов Y в С, 36 000 галлонов Z в С.

14. Минимальное число ткачей 26: 4 ткача начинают в первую смену; 10 - во вторую; 8 - в четвертую; 4 - в пятую или 4 начинают в первую смену; 4 - во вторую; 6 - в третью, 1 - в четвертую, 11 - в пятую.

15. Допустимых решений нет.

3.4. УПРАЖНЕНИЯ 1. а) 5500 т сырья типа А, 4500 т сырья типа В; 6) 100 дол.

4. x1 = 4,. За сырье А следует заплатить 0,6 (услов ных единиц); за сырье В - 1,2 (условных единиц).

Дополнительные часы работы составляют на машине 1: 7/5; 11: 1/5.

6. Лесопилка - 0; сборочный цех - 1 дол.; отделочный цех - 7 дол; x1 = 150, 7. 2700 студентов своей страны, 2150 иностранных. Да, это выгодно.

8. 1) 3/5, 1/5; 2) 10. Допустимых решений нет.

15. E получается удалением из F последних строки и столбца.

4.5. УПРАЖНЕНИЯ xij - количество стали (тыс. т), поставляемое потребителю C i - из x 4. xij - количество должностей в группе Pi, заполненных персоналом из группы S j.

Оптимальное решение x12 = 5, x14 = 1, x15 = 2, x25 = 3, x31 = 3, x34 = 4, x43 = 1 с 23 удовлетворительными назначениями и двумя неудовлетворительными назначениями в группе s5.

5. xij - количество изделий, тыс., произведенных фабрикой Fi, которые посылаются заказчику C j ; x11 = 10, x14 = 30, x 6. 10 000 изделий фабрики F1, потребителю C1, 6000 - C 2 ; 7000 изделий фабрики F2 потребителю C 2, 7000 - C 3, 2000 изделий из последних 7000 производятся сверхурочно.

7. Авиалинии: I-10 полетов в Бейрут, 10 - в Даллас; II - 10 полетов в Сидней, 10 Калькутту, 10 - в Бейрут; III - 5 полетов в Калькутту, 15 - в Сан-Паулу. Минимальная цена равна 86 000 (условных единиц).

8. Заводы посылают потребителям стали: I - 500 т С, 450 т Е; II - 300 т D; III - 1000 т В, 350 т D, IV - 250 т А, 200 т С.

9. Завод 1 посылает в августе 420 единиц продукта потребителю 1, 50 единиц продукта пользователю и сохраняет 30 единиц продукта для отправки потребителю в сентябре. Завод II посылает в августе 300 единиц продукта пользователю 2. Завод I посылает в сентябре единиц продукта пользователю 1 вдобавок к 30, сохранившимся с августа. Завод II посылает в сентябре 480 единиц продукта пользователю 2.

10. А: 1500 в W, 2500 в Y;

5.4. УПРАЖНЕНИЯ 3. Оптимальные маршруты грузовиков:

4. Соответствие отметок самолетам: Р1-А2, Р2-А2, РЗ-А4, Р4-А1.

5. Среда до полудня - в А, среда после полудня - в D, четверг до полудня - в С, четверг после полудня - в В, пятница до полудня - в Е.

6. Оптимальное соответствие номеров самолетов и авиалиний:

для города С: 2-12,6-11;

для города В: 1-9, 3-10,4-7, 5-8;

для города А: 7-4,11-5, 8-6,9-1,12-2,10-3.

7. Оптимальное распределение заданий по рабочим: задание 1 - для 5-го рабочего;

задание 2 – для 4-го; задание 3 - для 1-го; задание 4 – для 7-го; задание 5 - для 2-го; задание - для 3-го; задание 7 - для 6-го рабочего. Общее время 111ч.

8. Направить: А в область 1, В в область 2, С в область 3, D в область 6, Е в область 5.

6.5. УПРАЖНЕНИЯ 6. а) В выпуске деталей; б) Новое расписание: x1 = 90, x 2 = 30, x 7. x1 = 50, x 2 = 50, x3 = 50 ; прибыль равна 2500 дол.

8. а) Занять 10 105 акров культуры 1 на земле типа I, 4 105 акров культуры 2 на земле типа I, 12105 акров культуры 3 на земле типа II. Все земельные и водные ресурсы используются полностью, однако остаются не занятыми 105 человек, более 14 % доступной рабочей силы.

б) Каждые 105 акров земли типа I дают 2 дополнительные единицы дохода. Каждые единиц воды дают 2 дополнительные единицы дохода.

в) Да. Это увеличивает доход на 11 единиц (с 152 до 163 ). В новом решении типа I и акров новой культуры на земле типа II. Теперь рабочая сила используется полностью, а земля типа II - не полностью.

Марка красного вина Количество бутылок столового вина, тыс. бутылок Прибыль равна 490 133, 33 фунтов стерлингов.

7.4. УПРАЖНЕНИЯ и функция 18 y1 + 30 y2 + 27 y3 имеет максимальное значение.

2. Найти y1, y2, y3, где y1 0, y3 0 и y2 не ограничен в знаке, такие, что и функция 22 y1 + 9 y2 18 y3 имеет максимальное значение.

Для двойственной задачи: найти такие y1 0, y2 0, y3 0, что и функция 11 y1 + 20 y2 + 11 y3 = w должна быть максимальна.

6. Двойственная задача: найти такие y1 0, y2 0, что и функция y1 2 y2 имеет максимальное значение; допустимого решения нет.

8. Прямая задача: найти такие x1 0, x 2 0, что и функция 7 x1 + 3 x 2 имеет минимальное значение; допустимого решения нет.

Двойственная задача: найти такие y1 0, y2 0, что и функция 4 y1 + 2 y2 имеет максимальное значение; допустимого решения нет.