WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Pages:     | 1 | 2 ||

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

-- [ Страница 3 ] --

Для нее требуются 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 имеет максимальное значение; допустимого решения нет.



Pages:     | 1 | 2 ||


Похожие работы:

«МЕЖДУНАРОДНОЕ БЮРО ТРУДА GB.301 301-я сессия Административный совет Женева, ноябрь 2008 г. Повестка дня и программа заседаний GB Административный совет Повестка дня 1. Утверждение протоколов 300-й сессии Административного совета. 2. Дата, место проведения и повестка дня 99-й сессии (2010 г.) Международной конференции труда. 3. Обзор ежегодных докладов, подготавливаемых в рамках мер по реализации Декларации МОТ об основополагающих принципах и правах в сфере труда. 4. Реализация плана действий...»

«МИНИСТЕРСТВО КУЛЬТУРЫ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ЧЕЛЯБИНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ КУЛЬТУРЫ И ИСКУССТВ Согласовано Утверждаю Ректор В. Я. Рушанин (должность работодателя) _ 2014 г. (подпись) (И. О. Ф.) _ 2014 г. (должность работодателя) (подпись) (И. О. Ф.) _ 2014 г. (должность работодателя) (подпись) (И. О. Ф.) _ 2014 г. Основная образовательная программа высшего профессионального...»

«ПРОГРАММА СОХРАНЕНИЕ И УКРЕПЛЕНИЕ ЗДОРОВЬЯ ОБУЧАЮЩИХСЯ И ВОСПИТАННИКОВ ОБРАЗОВАТЕЛЬНЫХ УЧРЕЖДЕНИЙ КРАСНОСЕЛЬСКОГО РАЙОНА 1. Обоснование необходимости реализации программы на территории района Социально-экономическая ситуация на территории района характеризуется его окраинным положением на карте Санкт-Петербурга. Красносельский район является спальным районом города, удаленным от центра города (ближайшая станция метро Проспект Ветеранов в Кировском районе), здесь расположены около 30 небольших...»

«Пояснительная записка 11 класс Рабочая программа составлена на основе обязательного минимума содержания основного общего и среднего (полного) образования по биологии с учётом Федерального компонента государственного стандарта основного общего образования по биологии (приказ Минобразования РФ от 5 марта 2004г. №1089), примерной программы основного общего образования по биологии (профильный уровень), опубликованной на сайте Минобразования РФ и программы учителя биологии Бетиной Т.В. утвержденной...»

«Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования ОМСКИЙ ГОСУДАРСТВЕННЫЙ Утверждаю по УМР ОмГТУ JI.O. Штриплинг оС 20 1> год РАБОЧАЯ ПРОГРАММА по дисциплине УПРАВЛЕНИЕ ЛОГИСТИЧЕСКИМИ СИСТЕМАМИ (М. 1.02.02) 080100.68 - Экономика Магистерская программа: М.1. Экономика фирмы и отраслевых рынков Разработана в соответствии с ООП по направлению подготовки магистратуры 080100.68 Экономика (магистерская программа: экономика фирмы и отраслевых рынков)...»

«Страновой Многосекторальный Координационный Комитет По социально-значимым и особо опасным инфекционным заболеваниям при Правительстве КР Министерство здравоохранения КР Выполнение Декларации о приверженности делу борьбы с ВИЧ/СПИДом (ССГАООН) Страновой отчет Отчетный период: январь 2008 -декабрь 2009 гг. КЫРГЫЗСКАЯ РЕСПУБЛИКА Дата представления: 31 марта 2010 года Бишкек - март 2010 I. Содержание Информация об организации отчета 3 Список сокращений 4 Краткий обзор 5 Обзор эпидемии ВИЧ/СПИДа...»

«Министерство образования и науки Российской Федерации УДК: 539.23, 539.216.1, 621.787: 621.789 ГРНТИ: 29.12.22, 55.03.05, 55.20.27, 55.22.29 Инв. № УТВЕРЖДЕНО: Исполнитель: Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования Кузбасский государственный технический университет имени Т.Ф. Горбачева От имени Руководителя организации _/ В.А. Ковалев/ М.П. НАУЧНО-ТЕХНИЧЕСКИЙ ОТЧЕТ о выполнении 6 этапа Государственного контракта № 16.740.11.0641 от 02...»

«Учреждение образования Брестский государственный университет имени А.С. Пушкина ПРОФЕССИОНАЛЬНЫЕ НАВЫКИ ЮРИСТА Учебная программа для специальности 1-24 01 02 Правоведение 2010 СОСТАВИТЕЛЬ: С.М. Монич, преподаватель кафедры уголовно-правовых дисциплин учреждения образования Брестский государственный университет имени А.С.Пушкина РЕЦЕНЗЕНТЫ: Д.С. Береговцова, заведующая кафедрой истории государства и права юридического факультета учреждения образования Брестский государственный университет имени...»

«Менингококовые вакцины: полисахаридные и полисахаридные конъюгированные вакцины Документ по позиции ВОЗ ВОЗ предлагает информацию и рекомендации по вакцинам, используемым в Расширенной программе иммунизации (РПИ). В соответствии со своим глобальным мандатом организация выпускает серию регулярно обновляемых документов по позиции ВОЗ относительно других вакцин и их комбинаций против болезней, имеющих международное значение для общественного здравоохранения. Эти документы, в первую очередь,...»

«МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ И СОЦИАЛЬНОГО РАЗВИТИЯ РФ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ЗДРАВООХРАНЕНИЮ И СОЦИАЛЬНОМУ РАЗВИТИЮ ГОУ ВПО КИРОВСКАЯ ГОСУДАРСТВЕННАЯ МЕДИЦИНСКАЯ АКАДЕМИЯ ДЕПАРТАМЕНТ ЗДРАВООХРАНЕНИЯ КИРОВСКОЙ ОБЛАСТИ АКТУАЛЬНЫЕ ВОПРОСЫ СОВРЕМЕННОЙ БИОХИМИИ Всероссийская научно-практическая конференция биохимиков и специалистов по лабораторной медицине, посвященная 20-летию Кировской государственной медицинской академии (18-19 октября 2007 года) ПРОГРАММА и ПРИГЛАСИТЕЛЬНЫЙ БИЛЕТ Киров-2007...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Саратовский государственный аграрный университет имени Н.И. Вавилова СОГЛАСОВАНО УТВЕРЖДАЮ Заведующий кафедрой Декан факультета /Дружкин А.В./ _ /Трушкин В.А./ _ _20 г. _ 20 г. РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ) Дисциплина ПЕДАГОГИКА Направление 270800.62 Строительство Профиль подготовки Экспертиза и управление недвижимостью Квалификация...»

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА  МЕХАНИКО  МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ  ПРОГРАММА ВСТУПИТЕЛЬНОГО ЭКЗАМЕНА В МАГИСТРАТУРУ  НА 2011/2012 ГОД ПО НАПРАВЛЕНИЯМ   МАТЕМАТИКА, МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ    1. Непрерывность функций одной переменной, свойства непрерывных функции.  2. Функции многих переменных, полный дифференциал и его геометрический смысл.  Достаточные условия дифференцируемости. Градиент.  3....»

«Утверждаю: начальник управления развития животноводства, КФХ, ЛПХ, товарного рынка, заместитель председателя Конкурсной комиссии А.А. Курзанов ПРОТОКОЛ заседания Конкурсной комиссии 24 августа 2012 года 10-00 часов Комиссия в составе: Курзанов А.А. – начальник управления развития животноводства, крестьянских (фермерских), личных подсобных хозяйств, товарного рынка Министерства сельского хозяйства и продовольствия Омской области (председательствующий); Макаров Н.С. – начальник сектора развития...»

«30.11.2005 № 9/4625 -23РЕШЕ НИЕ ВИТЕБСКОГО ОБЛА СТНОГО СОВЕТА ДЕ ПУТАТОВ 23 июня 2005 г. № 126 9/4625 О Витебской областной программе возрождения и развития села на 2005–2010 годы (16.11.2005) Во исполнение Указа Президента Республики Беларусь от 25 марта 2005 г. № 150 О Государственной программе возрождения и развития села на 2005–2010 годы, в целях создания условий для приоритетного социально-экономического развития села, повышения эффективности работы агропромышленного комплекса Витебский...»

«5. Материалы заданий Олимпиады школьников Шаг в будущее (техника и технологии) Олимпиада школьников Шаг в будущее по направлению техника и технологии проводил Московский государственный технический университет имени Н.Э.Баумана (научно-образовательные и академические соревнования) при участии Калужского филиала МГТУ им. Н.Э.Баумана (академическое соревнование), Московского государственного текстильного университета им. А.Н.Косыгина (академическое соревнование), Липецкого государственного...»

«Федеральное агентство по образованию Федеральное государственное образовательное учреждение высшего профессионального образования Сибирский федеральный университет УТВЕРЖДАЮ Директор Института космических и информационных технологий _/ Г. М. Цибульский / 05 мая 2008 г. УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ Дисциплина Методы обработки экспериментальных данных (наименование дисциплины в соответствии с ФГОС ВПО и учебным планом) Укрупненная группа 230000 – Информатика и вычислительная техника (номер и...»

«CommView ® Remote Agent Руководство пользователя Copyright © 2001-2012 TamoSoft Введение О программе CommView Remote Agent Программа CommView Remote Agent предназначена для наблюдения трафика в удалённой сети. Она позволяет пользователям программы CommView анализировать сетевой трафик на компьютере, где запущен Remote Agent, где бы физически этот компьютер ни был расположен. Эта новая уникальная технология расширяет ваши возможности, поскольку теперь вы не ограничены только вашим компьютером...»

«М.М. Гинзбург Современная стратегия стройности Идеальная диета – ни один из продуктов не запрещен ни на один день! Самара 2008 г. 2 Как вы думаете, можно ли худеть, не испытывая при этом мучений? Можно ли обойтись без жестких диет и изматывающих физических нагрузок? Да, можно! И даже нужно! Подтверждением тому служат истории сотен пациентов, навсегда избавившихся от лишних килограммов. Автор этой поистине революционной методики, практикующий врач, доктор медицинских наук Михаил Моисеевич...»

«1 2 Программа вступительного испытания поступающих на заочную форму обучения на основе профессионального образования на направление 40.03.01 Юриспруденция 1. ОБЩИЕ ПОЛОЖЕНИЯ Характеристика программы вступительного испытания Вступительное испытание, проводимое университетом самостоятельно для поступающих на обучение по программе подготовки бакалавров на основе профессионального образования по направлению подготовки 40.03.01 Юриспруденция, предназначено для выпускников образовательных учреждений...»

«1. Пояснительная записка 1.1. Краткая характеристика дисциплины Курс История художественной культуры России ХХ века является одной из базовых учебных дисциплин в подготовке специалиста-культуролога. Программа составлена в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования по соответствующему направлению. Изложение и изучение материала курса История художественной культуры России ХХ века предполагает применение системного, комплексного...»






 
2014 www.av.disus.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.