Курс лекций - Математическое моделирование технических объектов (1075784), страница 21

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 21)

Пустьраничение:iri lni 1ln qiОпределим теперь коэффициент ri:. Полученные значения ri могут оказатьсядробными.Рассмотрим числовой пример.Система состоит из 3-х блоков, P  0,9.G1=1G2=3G3=1q1=0,3q2=0,5q3=0,5При каких ri будет обеспечен заданный уровень надежности и минимальный вес? Решение.Вычисляем i:i  1Q0G1 0,83;  2  4,32;  3  1, 44ln q1.n  , P ( r )  Q( r )  1  Qi0 1  0,9  0,1;   65,9Определяем : Gri   i ln i  1, ln qi   i ; r1  2, 64; r2  2,92; r3  4,5Gi iСоставляем таблицу для перебора оставшихся вариантов и выбора оптимального:i 1108№r1r2r312242225323442355324632573348335Варианты 1,2,3,4,5 не удовлетворяют требованиям надежности.

ИЗ оставшихся выбираем вариант с наименьшим весом.11.5 Симплекс-методСимплекс-метод позволяет решать задачи линейного программирования формально.Вначале рассмотрим несколько примеров применения симплекс метода. примерах покрытиянекоторой логической схемы элементами с заданным базисом.Рис.

1Рис. 2Пример № 1 Требуется покрыть логическую схему (рис.1) микросхемами 1ЛБ1011 и1ЛБ1012 (рис.2). Пусть m — число типов ЛЭ, i — номер типа ЛЭ. Обозначим n — число типов корпусов.В общем случае логическая схема содержит bi логических элементов i-го типа (в нашемслучае b1=5, b2=2). B — вектор состава ЛЭ схемы, B=(b1, b2)=(5; 2).При переходе к принципиальной электрической схеме надо все элементы распределитьпо k корпусам, причем в корпусе j-го типа могут находиться логические элементы либо одного, либо двух типов.Обозначим число логических элементов i-го типа в корпусе j-го типа Aij, и построимматрицу состава корпусов (1), котрая для данного примера имеет вид (2).Требуется покрыть вектор B, взяв xj корпусов j-го типа так, чтобы общее число корпусов Kбыло минимально.

Целевая функция в таком случае принимает вид (3):A  aijmnA2 10 1nK   x j  minj 1na xj 1ijj biK  x1  x2  min12345Вектор B вводит естественное ограничение на функцию цели (4). В противном случае,какой-либо ЛЭ останется вне корпуса. Функция K линейна относительно xj, поэтому задачаназывается задачей линейного программирования.109Для решения отбросим сначала требования целочисленности решения. После получениядробного результата рассмотрим все возможные дискретные точки в плоскости x1Ox2.

Функция цели для данного примера имеет вид (5).Сформулируем ограничения для данной задачи.Исходная логическая схема содержит 5 ЛЭ 1-го типа. Если взять x1 корпусов 1-го типа иx2 корпусов 2-го типа, то они дадут (2x1+x2) ЛЭ 1-го типа.

Тогда (2x1+x2)5. Например, если(2x1+x2)=3, то два ЛЭ схемы останутся без корпусов. Аналогично, для ЛЭ 2-го типа имеемx22. Решаем задачу графически. Строим область допустимых значений в плоскости x1Ox2.Функция K линейно увеличивается. В данном случае линия решений K пересекает область допустимых решений в точке A(1,5; 2). Т.к. мы получили дробный результат, то исследуем ближайшие целочисленные варианты:x1=1, x2=3x1=2, x2=2Оба варианта эквивалентны по числу корпусов, но число незадействованных выводов впервом случае — k1=4, а во втором — k2=3.Пример № 2 Фирма планирует получить прибыль z(x1,x2) от производства х1 тонн цветнойплитки и х2 тонн – обычной.Пусть прибыль от производства одной цветной плитки составляет $3, а от производстваодной обычной – $2.

Тогда z(x1,x2)=3x1+2x2 – целевая функция. Возможность получения максимального значения z ограничивают ресурсы предприятия: tm = 10 ч.- время работы оборудования; tn = 24 ч. – время работы персонала; q = 8 литров – объём цветной краски.Известно, что при производстве тонны цветной плитки оборудование работает 2 ч, персонал – 3 часа и расходуется 3 литра цветной краски. При производстве 1 тонны белой плитки:оборудование работает 1 час, персонал – 3 часа и краски не надо.Формальное ограничение ресурсов: x10 (объем производства цветной плитки не может быть отрицательным); x20 (объем производства белой плитки не может быть отрицательным); 2x1 + x2  10 – в противном случае для производства какой-то плитки не хватитьвремени работы оборудования; 3x1 + 3x2  24 – в противном случае для производства какой-то плитки не хватить времени работы персонала; 2x1 + 0x2  8 – иначе для производства цветной плитки не хватить краски;Каждая пара (x1, x2) удовлетворяющая этим ограничениям называется допустимым решением или программой.

Так как прибыль должна быть максимальной, имеем:z(x1, x2) =3x1 +2x2  maxИзобразим все прямые, задаваемые ограничениями, на плоскости в системе координатx1Ox2 (рис.1). Область допустимых решений (ОДР) на этом графике заштрихована – в каждойточке этой области соблюдаются все 5 ограничений. Построим на той же плоскости линию3x1 +2x2 = 0 или, что то же, x2= –1,5x1, соответствующую значению целевой функции $0(начало производства).110Начало производства плитки приводит к тому, что x1 и/или x2 становятсяположительными. Положительной становится и прибыль z(x1, x2). Пусть значение прибыли составило z(x1, x2) =const. Линия:3x1 +2x2 = const1.1пройдет правее линии z = 0, сместившись в направлении S, но с тем же наклоном (тангенс угла наклона осталсяпрежним).Известно, что значение const вфункции (1.1) примет оптимальное значение в точке пересечения линии (1.1) содной из вершин многоугольника, огРис.1раничивающего ОДР.Непосредственной проверкой убеждаемся, что оптимальное решение находиться в узле А,в котором все ресурсы, кроме краски исчерпаны.Рассмотрим аналитическое решение задачи симплекс–методом.1.

Преобразуем неравенства–ограничения в равенства, введением так называемых свободных переменных у1, у2 и у3.2х1+х2+у1=103х1+3х2+у2=24(*)2х1+0х2+у3=8Система уранений (*) содержит 5 переменных и любое их значение, удовлетворяющееуравнениям (*) является допустимым решением. В частном случае, перед началом производства основные переменные х1 и х2 равны нулю, а свободные (у1, у2 и у3), как это следует изсистемы (*), равны соответственно у1=10, у2=24 и у3=8. Полученное решение называется начальным допустимым решением (НДР), дающим нулевую прибыль: z(x1, x2) =3x1 +2x2=0.1) Полученное НДР сводим в симплекс-таблицу (табл.1).Таблица 1Таблица 2у3х2Ресурсых1 х2Ресурсы21у1=10 (машинное время)–11 2 =у1(машинное время)33у2=24 (рабочее время)20у3=8 (краска)32z =0 (– прибыль)–1,5312= у2 (рабочее время)0,504= х1(объем цв.)–1,52–12= z (– прибыль)Строки 1, 2 и 3 симплекс–таблицы представляют матричную форму записи системы уравнений (*).

Последняя строка – представляет значение прибыли. В столбце 3 представленособственно НДР, которе можно улучшить, например, производством плиток одного из двухтипов. Из первой строки симплекс–таблицы видно, что на производство одной тонны цветной плитки расходуется 2 часа машинного времени. Наличное машинное время (у1=10) ограничивает производство цветной плитки количеством 10/2=5 тонн. Аналогично вторая и третья строки ограничивают производство цветной плитки восемью и четырьмя тоннами. Элемент, стоящий на пересечении столбца х1 и строки у3 называется ограничивающим элемен-111том или центром.

Строка и столбец, на пересечении которых находится центр называютсяцентральными.Решение х1=4, х2=0 (точка A на графике) даст прибыль z =3×4+2×0=12. Чтобы получитьсимплекс-таблицу, соответствующую новой программе, выполнм замену переменной у3 на х1из центрального уравнения: х1=4 – 0,5у3 . Подставив далее полученное выражение в систему(*) и целевую функцию и получим систему:2(4 – 0,5у3)+х2+у1=10– у3 + х2 + у1 = 23(4 – 0,5у3)+3х2+у2=24–1,5у3 + 3х2 + у2 = 122х1 + у3 = 80,5у3 + х1 = 4z=3(4 – 0,5у3) +2x22x2 – 1,5у3 +12 = zПолученной системе соответствует симплекс-таблица, представленная в табл.2. Элементы, стоящие во втором столбце показывают, что для производства одной тонны плитки второго типа потребуется один дополнительный час машинного времени, 3 часа рабочего и этоне приведёт к сокращению производства плитки первого типа.

Доход от такого производствасоставит 2.Первый столбец показывает, что для экономии одного 1 литра краски нужно использовать 1 час машинного времени и 1,5 часа рабочего времени и всё это приведёт к сокращению производства плиток первого типа на 0,5 тонны и уменьшению прибыли на 1,5.Это решение можно улучшить, начав производство обычной плитки. Объем ее производства ограничивает ресурс оставшегося машинного времени в количестве 10–(2×4)=2 часа, которого хватит на производство 2-х тонн обычной плитки. Программа х1=4, х2=2 даст прибыль z=3×4 +2×2=16 и уменьшит ресурс рабочего времени до 12–(3×2)=6 часов, которого хватилобы на производство 2-х тонн обычной плитки (точка B на графике).

Далее повысить прибыльможно, снизив объем производства цветной плитки и (за счет высвобождающегося ресурсамашинного времени) увеличить объем производства обычной плитки. Последняя дает в 1,5раза меньше прибыли на тонну, чем цветная, но при том же ресурсе машинного времени ееможно произвести в 2 раза больше.

Если уменьшить х1 на 1 в программе х1=4, х2=2, то можнореализовать программу х1=3, х2=4, и получить прибыль z =3×3 +2×5=17 вместо 16.Опишем алгоритм выполнения очередной итераций преобразования симплекс–таблицы.Исходную симплекс-таблицу будем называть «старой», а результирующую – «новой». Описание будем сопровождать примером формального преобразования таблицы 1 в таблицу 2.Предварительно представим исходную симплекс-таблицу (табл.1) в компактном виде (рис.2)и введем ряд обозначений:A – центр;B=1/A – величина, обратная центру;Dij –элемент на пересечении i-й строки и j-го столбца симплекс-таблицы;Ri – элемент i-й строки столбца ресурсов симплекс–таблицы;Qi – элемент i-й строки центрального столбца симплекс-таблицы;Pj – элемент j-го столбца центральной строки симплекс-таблицы;S(S) – элемент старой (новой) симплекс-таблицы.Алгоритм:1.

Характеристики

Список файлов лекций