|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
|
|
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Основные результаты линейного программирования ⇐ ПредыдущаяСтр 10 из 10
Опуская строгие математические доказательства, сформулируем основные утверждения линейного программирования. 1. Если ограничения имеют допустимые решения, то они имеют и базисное решение. 2. Допустимая область является выпуклым множеством. 3. Базисные допустимые решения соответствуют вершинам выпуклого множества. 4. Если целевая функция имеет конечный минимум, то по крайней мере одно оптимальное решение является базисным.
Симплекс – метод при заданном допустимом базисном решении
Графический метод решения невозможно применить к задачам с размерностью более трех. Предлагаемый алгоритм решения задач, разработанный Г. Данцигом, является вычислительной процедурой, представленной в алгебраической форме. Рассмотрим сначала алгоритм решения задач подобного типа на примере, а затем сформулируем общие закономерности. Повторим условия упражнения №7: максимизировать функцию Z=2X1+4X2 при ограничениях: X1≥ 0, X2≥ 0, 3X1+4X2≤ 1700, X1+5X2≤ 1600. В стандартной форме с неотрицательными дополнительными переменными X3 и X4 ограничения и целевая функция принимают вид 3X1+4X2+X3=1700, (34) 2X1+5X2 +X4=1600, (35) –2X1–4X2 =Z. (36) Очевидно, что набор X1=X2=0, X3=1700, X4=1600 образует базисное решение. Функция Z, имеющая нулевое значение, выражается через небазисные переменные, которые также имеют нулевые значения. Зададим себе вопрос, каким образом можно уменьшить значение функции Z? Поскольку в уравнении целевой функции коэффициенты при X1 и X2 отрицательны, а сами X1 и X2 должны быть неотрицательны по ограничениям, то любое увеличение значений X1 и X2 будет приводить к уменьшению функции Z. Для упрощения алгоритма решения задачи увеличивается значение только одной из переменных. В качестве таковой может выступать любая, но предпочтение следует отдавать переменной с большим по модулю коэффициентом, то есть переменной X2. Однако, при увеличении значения X2 будут изменяться значения X3 и X4 в силу необходимости выполнения ограничений (34-36). Все переменные должны оставаться неотрицательными. Таким образом, существует предел увеличения X2. Поскольку 3X1+4X2+X3=1700, X3 обращается в ноль при X2=1700/4=425 (напоминаем, что X1=0). Из (35) X4=0 при X2=1600/5=320. Таким образом, X2 не может увеличиваться сверх 320, в противном случае переменные приобретают отрицательные значения. Проведем ряд преобразований с уравнениями (34)-(36). Цель преобразований – сделать переменную X2 базисной с коэффициентом единица в уравнении (35) и исключив переменную из всех остальных уравнений. Разделив (35) на 5, получим 2/5X1+X2+1/5X4=320 (37) Если теперь умножить (37) на 4 и вычесть результат из (34), получим 7/5X1+X3–4/5X4=420. Если теперь (37) умножить на (–4) и вычесть результат из выражения целевой функции (36), получим –2/5X1+4/5X4=Z+1280. Таким образом, ограничения и целевая функция принимают вид 7/5X1+X3–4/5X4=420, (38) 2/5X1+X2+1/5X4=320, (39) –2/5X1+4/5X4=Z+1280. (40) Переменная X2 исключена отовсюду, кроме (39), куда она входит с коэффициентом единица, что является канонической формой для базиса X2 и X3, представляющего базисное допустимое решение. Небазисными переменными в каноноческом виде стали X1 и X4. В данном случае их можно приравнять нулю. Теперь значение целевой функции можно уменьшить, увеличивая только X1. Для ограничения (38) X3=0 при X1=300; для ограничения (39) X2=0 при X1=800. Исходя из этого, максимальное увеличение X1 составляет 300. Разделив (38) на коэффициент при X1=7/5, получим X1+5/7X3–4/7X4=300. (41) Теперь исключим X1 из другого ограничения и целевой функции, вычитая выражение (41), умноженное на 2/5 и минус 2/5, из соответствующих ограничений, получим каноническую форму задачи для базиса X1 и X2: X1 +5/7X3– 4/7X4=300, X2–2/7X3+ 3/7X4=200, (42) 2/7X3+ 4/7X4=Z+1400. Дальнейшее увеличение X3 и X4 не приведет к снижению целевой функции и при X3=X4=0 функция Z имеет минимальное значение –1400 при допустимом базисном решении X1=300; X2=320. Приведенный итерационный процесс удобно иллюстрировать так называемыми симплекс-таблицами. Таблица 12
Примечание. Знаком [0] в таблице отмечены коэффициенты, которые на очередной итерации собираемся обратить в базисные переменные; знаком [*] отмечены переменные, которые должны иметь нулевое значения в отличии от тех, которые обращаются в ноль при проведении преобразований.
Обобщение результатов линейного программирования
Предположим, что начальная каноническая форма задана уравнениями, в которых ограничения преобразованы таким образом, что X1,..., Xn последовательно выражаются через b и остальные Xi. Это можно записать в виде
X1+...…..a'1(m+1)X(m+1)+...+a'1nXn=b'1 (43) Xm+a'm(m+1)X(m+1)+...+a'mnXn=b'n Если умножить ограничения системы (43) на с1, с2,..., сm и вычесть из Z, то X1,..., Xm исключаются из Z и мы получим
c'm+1Xm+1+c'm+2Xm+2+...+c'nXn=Z–Zo, (44) где m Zo= å ci*bi. (45) i=1
Если Xm+1, Xm+2,..., Xn=0, то соотношения X1=b'1, X2=b'2, Xm+1=0, Xn=0 задают базисное решение. Если же при этом все b'i≥ 0 – это решение допустимо. Среди таких решений надо найти оптимальное. Симплекс-метод обеспечивает процедуру замены одной канонической формы на другую, при которой значение целевой функции уменьшается. В виде симплекс таблиц уравнения (43)-(45) приведены ниже.
Таблица 13
Итерационный процесс состоит из трех шагов. 1. Найти переменную для включения в базис. Таковой будет небазисная переменная, для которой с'j≤ 0 (лучше максимальная по модулю с'j. Пусть это будет с'm+1. 2. Найти переменную для исключения из базиса. Для этого необходимо найти ответ на следующий вопрос: насколько можно увеличивать Xm+1, не нарушая условия неотрицательности базисных переменных? Если в i-том ограничении a'(m+1)> 0, то наибольшее значение, которое может принимать Xm+1 равно b'i/a'i(m+1), иначе переменная Xi станет отрицательной. Таким образом значение Xm+1 может быть увеличено до величины {max}Xm+1={min}(b'i/a'1(m+1)) при i=1...m, a'i(m+1)> 0. Если этот минимум достигается в строке r, то Xr обращается в ноль, когда Xm+1= b'r/a'r(m+1). Элемент a'r(m+1) называется ведущим элементом, строка r – ведущая строка, столбец m+1 – ведущий столбец. 3. Построение новой канонической формы. Теперь получили новый базис X1, X2, Xm, Xm+1. Чтобы построить новую каноническую форму, коэффициент при Xm+1 в ведущей строке сделаем равным единице, поделив строку на ar(m+1), чтобы образовать новую ведущую строку. Затем удалим Xm+1 из других ограничений целевой функции. Для этого из i строки (i≠ r) с коэффициентом a'r(m+1) при Xm+1 вычтем a'r(m+1) (новая ведущая строка). На очередной итерации каноническая форма будет выглядеть следующим образом табл.14) Таблица 14
Теперь, построив новую каноническую форму, необходимо вернуться к первому шагу итерационного процесса и вновь повторить вычислительную процедуру, выбрав отрицательное значение С+j. Итерационный процесс продолжается до тех пор, пока все cj не станут положительными. Это означает, что минимум целевой функции достигнут. Покажем работу алгоритма на упражнении № 9. В стандартной форме ограничения и целевая функция выглядят следующим образом. Минимизировать функцию – 6X1–2X2=Z (46) при ограничениях X1, X2, X3, X4> =0, (47) 2X1+4X2+X3=9, (48) 3X1+X2+X4=6. (49) Последовательность итераций с комментариями решения приводится в табл. 15. Таблица 15
Начальный базис очевиден: X1=X2=0; X3=9; X4=6. Желательной переменной для включения в базис является X1, так как для этой переменной значение коэффициента c1 в выражении целевой функции имеет максимальную отрицательную величину. При этом ведущим будет столбец с номером 1, ведущей строка с номером 2; значение коэффициента a21=3. Для включения в базис X1 разделим ведущую строку на 3, получим Х1+1/3Х2+1/3Х4=2. Исключим X1 из ограничения (48) и целевой функции (46), умножив Х1+1/3Х2+1/3Х4=2 на 2 и (–6) и вычтем соответственно полученные уравнения из ранее упомянутых. Получим, соответственно, новые выражения ограничения и целевой функции (табл. 15, итерация 1). В целевой функции коэффициент С4 имеет положительное значение, коэффициент С2 равен нулю, то есть включение X2 в базис не имеет смысла, так как это не уменьшит значение целевой функции. Покажем это на примере следующей итерации. Предлагаем читателю самостоятельно получить выражения ограничений и целевой функции для второй итерации. Значение целевой функции не изменилось. Если сравнить полученные результаты с рис. 9 для графического решения данного упражнения, то легко убедиться, что первая итерация соответствует точке С, вторая – точке В.
Транспортная задача
3.7.1. Постановка транспортной задачи
Упражнение № 12. Кирпичные заводы снабжают своей продукции стройки области. На заводах имеется 300, 400, 700 и 480 единиц продукции соответственно: а потребности строек составляют 170, 350, 450, 610 и 300 единиц. Стоимости перевозки единицы продукции в ценовом выражении с завода на стройку приведены в табл. 16. Таблица 16
Как следует спланировать перевозки продукции, чтобы общая стоимость перевозок была минимальной? Пусть Xij – количество продукции, которое будет отправлено с i-го завода на j-ю стройку. Очевидно, что Xij > = 0 и в силу ограничений на производство и потребление объемы перевозок будут удовлетворять следующим условиям: для производства X11+X12+X13+X14+X15=300, X21+X22+X23+X24+X25=400, X31+X32+X33+X34+X35=700, X41+X42+X43+X44+X45=480, для потребления X11+X21+X31+X41=180, X12+X22+X32+X42=350, X13+X23+X33+X43=450, X14+X24+X34+X44=600, X15+X25+X35+X45=300.
Целевой функцией задачи является общая стоимость перевозок Сt=16X11+18X12+12X13+19X14+24X15+...+11X41+18X42+22X43+15X44+9X45, которая должна быть минимизирована при указанных ограничениях. Эта задача является специальной задачей линейного программирования, так как коэффициенты в ограничениях могут принимать значения только ноль или единица и каждая переменная входит только в два ограничения. Кроме того, сумма объемов перевозок по первым четырем ограничениям равна сумме объемов потребления по пяти последним (равенство спроса и предложения). Все это обобщается на транспортную задачу с m пунктами производства и объемами производства ai (i=1,..., m), и n пунктами потребления с объемами потребления bj (j=1,..., n), при
Если Cij – стоимость транспортировки единицы продукции от i-го производителя j-му потребителю, то задача заключается в нахождении таких Xij ≥ 0, которые удовлетворяют соотношениям
и минимизируют функцию
Поскольку объемы производства и потребления совпадают, то имеется всего (m+n-1) независимых ограничений, и, следовательно, (m+n-1) базисных переменных в базисном допустимом решении.
3.7.2 Алгоритм решения транспортной задачи путем последовательного улучшения плана
При решении задачи удобно работать не с ограничениями в виде систем линейных уравнений, а с массивом данных в виде таблицы (см. табл. 16). Расчетная процедура включает в себя несколько этапов. 1. Поиск первого базисного допустимого решения. Поскольку задача состоит в минимизации целевой функции, для ускорения расчетов при определении первого базисного решения следует использовать правило " наиболее дешевая продукция перевозится в первую очередь". Минимальную стоимость имеет перевозка со второго завода на третью стройку и с учетом производства второго завода (400) и потребности третьей стройки (450) принимает; что X23= 400. Удаляем строку для второго завода (все, что на нем произведено, перевезено на третью стройку), а потребность третьей стройки уменьшаем на 400. И далее к измененному массиву повторяем процедуру определения объемов перевозок. После того, как последней переменной присвоено значение, сумма производства и потребления становится равной нулю, количество элементов, включенных в базисное решение, становится равным 8. Обращаю внимание читателей, что в процессе формирования базисного решения после очередного назначения величины Xij из массива удаляется либо одна строка (исчерпан объем производства завода), либо один столбец (удовлетворена потребность стройки). И только при назначении последнего (m+n-1 - го) элемента одновременно пропадают и строка и столбец. Только в этом случае будет обеспечено условие наличия (m+n–1) базисных элементов массива. Что делать, если в ходе формирования базисного допустимого решения на промежуточном этапе возникает необходимость удаления строки и столбца (оставшиеся объемы производства и потребления совпадают). Нормальный ход решения задачи приведет к включению в базисный вариант меньше, чем (m+n–1) ненулевых переменных Xij, что нарушает ограничения постановки задачи. Каков выход из этой ситуации? Их может быть два. Первый из них заключается в том, что при формировании базисного варианта при появлении указанной выше ситуации следует отклониться от правила преимущества распределения наиболее дешевой продукции и принять другое решение, исключающее одновременное вычеркивание из массива строки и столбца на промежуточном этапе. Так как первых допустимых базисных решений может быть много, такой подход правомерен. Второй возможный выход заключается во включении в базисный вариант любого Xij, приравняв его нулю, для обеспечения требуемого количества базисных элементов. При дальнейшей реализации алгоритма решения задачи этот нулевой объем перевозок пропадет. Вернемся к нашей задаче. В табл. 17 показан первый базисный вариант. Таблица 17
Стоимость перевозок, соответствующая базисному варианту, составляет 25520 единиц. Далее покажем, каким образом можно снизить величину стоимости. 2. Оценка возможности улучшения плана перевозок Возможность минимизации стоимости перевозок лежит в использовании так называемых симплекс-множителей (u множители по строкам и v множители по столбцам). Теория линейного программирования строго доказывает, что
из которого следует, что для занятых элементов массива справедливо соотношение Cij–ui–vj=0, и следовательно, можно определить ui и vj. Имеем m неизвестных симплекс-множителей ui и n неизвестных vj. А занятых элементов массива всего (m+n–1). Из этой ситуации можно выйти, приняв один из симплекс-множителей равным нулю и решив систему уравнений относительно других симплекс-множителей. Удобнее (но не обязательно) приравнивать нулю тот множитель, для которого либо в строке, либо в столбце имеется максимальное количество занятых элементов массива. Для рассматриваемого нами примера примем, что u4=0. Тогда из выражений: C41–u4–v1=0; C44–u4–v4=0; C45–u4–v5=0. имеем v1=11, v4=15, v5=9. И далее из уравнений: C34–u3–v4=0® u3=2; C32–u3–v2=0® v2=21; C12–u1–v2=0® u1= –3; C13–u1–v3=0® v3=15; C23–u2–v3=0® u2= –7.
Обычно значения симплекс-множителей указываются в скобках против или ниже соответствующих строк и столбцов массива. После определения симплекс-множителей для небазисных (не занятых) элементов массива рассчитывается дополнительная величина Cij’=Cij–ui–vj (55)
Если величина Cij’ для какого-либо незанятого элемента массива отрицательна, то включение данного элемента в базисный вариант приведет к уменьшению целевой функции. Если величина Cij’равна нулю, то включение данного элемента в базисный вариант не приведен к изменению целевой функции; и в случае, если Cij’ больше нуля, то включение данного элемента в базисный вариант будет увеличивать целевую функцию. Конечно же, нас интересует только первый вариант значений Cij’. Ниже показан расчет значений Cij’ для незанятых элементов массива нашего упражнения. C11=C11–u1–v1=16 – 11 – (–3)=8; C14=C14–u1–v4=19 – 15 – (–3)=7; C15=C15–u1–v5=24 – 9 – (–3)=18; C21=C21–u2–v1=14 – 11– (–7)=10; C22=C22–u2–v2=25 – 21– (–7)=11; C24=C24–u2–v4=23 – 15– (–7)=15; C25=C25–u2–v5=18 – 9– (–7)=16; C31=C31–u3–v1=19 – 11 – 2=6; C33=C33–u3–v3=21 – 15 – 2=4; C35=C35–u3–v5=25 – 9 – 0=14; C42=C42–u4–v2=18 – 21 – 0=– 3; C43=C43–u4–v3=22 – 15 – 0=7.
Таким образом, только включение X42 в базисный вариант может привести к снижению стоимости перевозок. Ясно, что для нашей задачи увеличение X42 на единицу будет уменьшать целевую функцию на 18. Но как определить максимальный объем X42, который бы не нарушил баланса производства и потребления. Если мы увеличиваем X42 на величину W, то строка 4 и столбец 2 должны соответственно уменьшиться на такую же величину. Таким образом, анализ возможности включения X42 в базисный вариант заключается в поиске такой замкнутой ломаной линии, во всех узлах которой находятся занятые элементы массива кроме узла с координатами (4, 2). Простейшая фигура – прямоугольник. Для нашего случая это прямоугольник указан на рис. 12.
Рис. 12. Схема варианта изменения объемов перевозок
В общем случае это может быть сложная ломаная линия. Поиск этой ломаной можно проводить следующим образом. В допустимом базисном варианте отметим желательный для включения элемент массива, как уже включенный в базис. После этого из матрицы последовательно удаляются строки и столбцы, в которых имеется только один занятый элемент (обращаю внимание, что после очередного удаления ситуация в матрице будет изменяться). По окончании этого циклического процесса в матрице останутся только те элементы, которые будут принадлежать замкнутой ломаной линии. Итак, мы определили возможность включения элемента X42 в базисный вариант. Для баланса производства и потребления мы вынуждены изменять объемы перевозок в занятых элементах массива на величину W, как это показано на рис. 12. Максимальная величина W не может быть больше 10, так как в противном случае значение X44 станет отрицательным. Таким образом, максимальная величина W, на которую изменяются объемы перевозок, будет равна минимальному объему перевозок тех элементов массива, из которых производится вычитание W. При этом один из ранее занятых элементов массива (в нашем случае X44) становится равным нулю, а количество занятых элементов массива в базисном варианте первого приближения останется равным m+n–1, то есть 8. Новый базисный вариант приведен в табл. 18.
Таблица 18
Полная стоимость, соответствующая этому варианту приближения составляет 25490, что меньше, чем в первом базисном варианте. Далее расчетная процедура повторяется до тех пор, пока все значения Cij’ небазисных элементов массива не будут больше нуля. Этот вариант распределения объемов перевозок продукции будет иметь минимальную стоимость, то есть будет оптимальным вариантом распределения. В рассматриваемом упражнении величины симплекс-множителей на втором шаге приведены в табл. 18, значения Cij’ приведены в соответствующих элементах матрицы. Ясно видно, что дальнейшее снижение стоимости перевозок невозможно, то есть вариант распределения объемов перевозок (табл. 18) является оптимальным с точки зрения минимальной стоимости. В некоторых случаях при реализации алгоритма последовательного улучшения плана возникает ситуация, когда включение желательного элемента матрицы в базисный вариант невозможно. В этом случае единственно возможной ситуацией получить оптимальное решение является изменение порядка расположения поставщиков или потребителей на стадии формулировки исходных данных. ОТВЕТЫ НА ЗАДАЧИ ПОСОБИЯ Задача № 1. Средние значения прочности одинаковы в обеих сериях и равны 20, 0 МПа. Коэффициенты вариации соответственно равны 4, 40 и 12, 0 %. Ошибка определения прочности во второй серии выше.
Задача № 2. Vp1=4, 39 %; Vp2=5, 46 %.
Задача № 3.
Задача № 4.
Среднее значение Vp по 10 сериям равно 11, 4 %.
Задача № 5. При n=8 значение R=40, 83; S(Ri)=4, 05; Rрасч=(9, 23/4, 05)=2, 28 При q=0, 95 Rmax=2, 17: результат 31, 6 – грубая ошибка При q=0, 99 Rmax=2, 37: результат 31, 6 – не является грубой ошибкой.
Задача № 6.
Задача № 8. Средние значения прочности по сериям С вероятностью не выше 0.99 вывод об увеличении прочности бетона при введении полифункциональной добавки обоснован. Задача № 9.
Задача № 10.2. Задача носит экстремальный характер. Задача № 11.Число состояний первого объекта 26=64; второго объекта 43=64. Сложность объектов одинакова. Задача № 12. Невозможно, так как между температурой и давлением существует нелинейная связь. Задача № 13. X1н = 75 С, X2н = 7 часов.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Банди, Б. Основы линейного программирования / Б. Банди. Пер. с англ. – М.: Радио и связь, 1989. –176 с. 2. Вознесенский, В.А. Численные методы решения строительно-технологических задач на ЭВМ: учебник / В.А. Вознесенский, Т.В. Ляшенко, Б.Л. Огарков; Под ред. В.А.Вознесенского. – Киев.: Выща школа, 1989. –328 с. 3. Грачев, Ю.П. Математические методы планирования экспериментов / Ю.П.Грачев. – М.: Пищевая промышленность, 1979. – 200 с. 4. Румшиский, Л.З. Математическая обработка результатов эксперимента / Л.З. Румшиский.–М.: Наука, 1971. –192 с. 5. Дэниел, К. Применение статистики в промышленном эксперименте /К.Даниэл; пер. с англ. – М.: Изд-во Мир, 1979. – 294 с. 6. Джонсон, Н. Статистика и планирование эксперимента в технике и науке: Методы планирования эксперимента / Н. Джонсон, Ф. Лион; пер. с англ. – М.: Мир, 1981 – 520 с. 7. Таблицы планов эксперимента для факторных и полиномиальных моделей: Справочник. /под ред. В.В. Налимова. – М.: Металлургия, 1982. – 752 с.
ПРИЛОЖЕНИЯ Приложение А Значение критерия максимального отклонения Rmax
Приложение Б Значение критерия α т для определения грубых ошибок
Приложение В Значение критерия Стьюдента t (P, f)
Приложение Г Значение критерия Кохрена G для уровня значимости q=0, 05
Популярное:
|
Последнее изменение этой страницы: 2016-03-22; Просмотров: 1162; Нарушение авторского права страницы
. (50)
, i=1…m, (51)
, j=1…n, (52)
, (53)
, (54)
24, 0; 
28, 4. S2R1=2, 40; S2R2=0, 71; Fрасч=3, 38; Fт=6, 3 – дисперсии однородны. T=3, 93.