Автоматихация производства ЭВА (1075779), страница 29

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

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

Требуется покрыть её микросхемами 1ЛБ1011 и 1ЛБ1012. Пусть m — количество типов ЛЭ, i — номер типа ЛЭ. Обозначим n — число типов корпусов.

1ЛБ1011	1ЛБ1012

В общем случае логическая схема содержит b_i логических элементов i-го типа (в нашем случае b₁=5, b₂=2).

B — вектор состава ЛЭ схемы, B=(b₁, b₂)=(5; 2).

При переходе от логической схемы к принципиальной необходимо все элементы распределить по k корпусам. В общем случае в корпусе j-го типа могут находиться логические элементы либо одного, либо двух типов.

Обозначим число логических элементов i-го типа в корпусе j-го типа A_ij, и построим матрицу состава корпусов: .

Для текущего примера .

Требуется покрыть вектор B, взяв x_j корпусов j-го типа так, чтобы общее число корпусов K было минимально. Целевая функция в таком случае принимает вид:

Вектор B вводит естественное ограничение на функцию цели:

В противном случае, какой-либо ЛЭ останется вне корпуса.

Функция K линейна относительно x_j, поэтому задача называется задачей линейного программирования.

Для решения отбросим сначала требования целочисленности решения. После получения дробного результата рассмотрим все возможные дискретные точки в плоскости X₁OX₂.

Функция цели для данного примера: .

Сформулируем ограничения для данной задачи.

1. Исходная логическая схема содержит 5 ЛЭ 1-го типа. Если взять x₁ корпусов 1-го типа и x₂ корпусов 2-го типа, то они дадут 2x₁+x₂ ЛЭ данного типа. Тогда 2x₁+x₂5. Аналогично, для ЛЭ 2-го типа имеем x₂2.

2. Решаем задачу графически. Строим область допустимых значений в плоскости X₁OX₂.

Функция K линейно увеличивается. В данном случае линия решений K пересекает область допустимых решений в точке A(1,5; 2). Т.к. мы получили дробный результат, то исследуем ближайшие целочисленные варианты:

x1=1, x2=3

x1=2, x2=2

Оба варианта эквивалентны по числу корпусов, но число незадействованных выводов в первом случае — k₁=4, а во втором — k₂=3.

Пример № 2:

Пусть фирма планирует произвести 2 вида плитки: х₁ голубой и х₂ обычной тонн. Для получения прибыли z(x₁,x₂). Если прибыль от одной цветной плитки составляет 3$, а от обычной 2$.

Тогда z(x₁,x₂)=3x₁+2x₂ – целевая функция.

Возможность получения максимального z ограничивают ресурсы предприятия:

t_m = 10 ч.- время работы оборудования;

t_n = 24 ч. – время работы персонала;

q = 8 литров – объём голубой краски.

При производстве 1 голубой плитки оборудование работает 2 часа, персонал работает 3 часа, расходуется три литра голубой краски.

При производстве 1 белой плитки: 1час работы оборудования, 2 часа персонала и 0 литров краски.

Формальное ограничение ресурсов:

Каждая пара (x₁, x₂) удовлетворяющая этим ограничениям называется допустимым решением (программой).

z=3x₁+2x₂max

Рассмотрим графическое решение задачи:

Изобразим все прямые, задаваемые ограничениями.

С  области допустимых решений.

1. z=12

Решение графическим методом. Найти, перемещая линию, параллельную самой себе до точки А.

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

Сущность метода.

Метод даёт аналитические решения для задач нелинейного программирования.

1. Преобразуем неравенства ограничения в равенства, введением переменных у₁,…,у₃.

2х₁+х₂+у₁=10

3х₁+3х₂+у₂=24

2х₁+0х₂+у₃=8

Примечание: другими переменными можно пренебречь., так как перед началом производства x₁=х₂=0, то есть у₁=10, у₂=24, у₃=8.

Полученное таким образом решение называется начальным допустимым решением, дающим нулевую прибыль.

1. Полученное допустимое решение сводим в симплекс таблицу.

Первые три строки – матричная форма записи исходной системы уравнений.

Последняя строка – прибыль. Начальное решение представлено последними двумя столбцами.

Это решение можно улучшить производством плиток одного из двух типов.

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

Элемент, стоящий х₁ и у₃ называется ограничивающим элементом (центр).

Поменяем местами х₁ и у₃ и получим новое решение, в котором х₁=4, а х₂=0. Эта операция потребует 8 часов машинного времени, 12 часов рабочего времени и краски.

z=12

Замена переменной у₃ на х₁ выполнена из последнего (центрального) уравнения.

х₁=4-0,5у₃

Подставим это в первое и третье уравнения целевую функцию и получим следующую СЛАУ:

Составляем новую таблицу:

Элементы, стоящие во втором столбце показывают, что для производства одной тонны плитки второго типа потребуется один дополнительный час машинного времени, 3 часа рабочего и это не приведёт к сокращению производства плитки первого типа. Доход от такого производства составит 2.

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

Воспользуемся данными, приведёнными во втором столбце (см. график, линия DB).

1. Выбираем центр, который удовлетворяет трём следующим условиям:

   1. центр находится в столбце, последний элемент которого положителен.

   2. центр должен быть ненулевым.

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

2. Образуем величину, обратную центру (1/центр), и в симплекс таблице заменяем центр на b.

3. Получаем новые элементы центральной строки, упрощая её элементы на b.

4. Определяем элементы центрального столбца, умножив соответствующие элементы на b.

5. Приходим к следующей симплекс таблице (b=1/2)

d_ij – элемент, лежащий на позиции (i,j) в таблице.

Четвёртая итерация решения выполняет следующие шаги:

1. В исходной таблице находим центр: он лежит в том столбце, в котором –z>0.

Если таких столбцов несколько, то в том, в котором частное от деления r_i/d_ij минимально.

10/2=5;

24/3=8;

8/2=4 — минимум;

10/1=10;

24/3=8;

8/0=∞.

Обозначим центр буквой О=d₁₃=2.

1. Формируем новую симплекс таблицу в следующем порядке:

а) Образуем величину, обратную центру b=1/O=0,5.

б) Выполняем обмен переменных на местах которыми стоит центр (в этом примере у₃х₁) и записываем на месте новой строки и столбца величину b.

в) Переписываем все элементы центральной строки пр. самого центра из старой строки симплекс таблицы в новую, попутно умножая их на b.

г) Обозначим элементы новой центральной строки через p_j.

p₁=b; p₂=0; p₃=4.

д) Вычисляем остальные элементы центрального столбца, попутно умножая их на b.

q_i – новый элемент центрального столбца, ^~q_i – старый.

q_i=^~q_i(-b)

^~q₁=2; ^~q₂=3; ^~q₄=3.

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

Список файлов книги