Характеристики исходных сплавов

 

Показатель	Исходные сплавы
Содержание свинца, % Содержание цинка, % Содержание олова, % Стоимость единицы сплава, денежных ед.

 

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

Сформулируем экономико-математическую модель данной задачи. Обозначим через х ₁ х ₂, x ₃ х ₄ х ₅искомые количества исходных сплавов. Тогда целевая функция примет вид:

 

 

При этом существуют следующие условия:

 

 

Сформулированная задача, как и предыдущая, решается методами линейного программирования.

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

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

L – длина исходного материала;

i – номер (индекс) вида требуемых заготовок, i = 1, 2... т;

l_i – длина заготовки i -го вида;

А_i – требуемое число заготовок i -го вида (не менее);

j - номер варианта раскроя, j = 1, 2... n;

a_j – количество заготовок i -го вида при раскрое единицы исходного материала по j -му варианту;

с_ij – длина отхода по j -му варианту.

Пусть х ₁ - количество единиц исходного материала, раскраиваемых по i -му варианту. Целевая функция по критерию минимума отходов имеет вид:

 

 

По критерию минимума раскраиваемых единиц исходного материала уравнение может быть таким:

 

 

Это верно при соблюдении следующих условий:

 

 

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

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

Наиболее трудоемкий этап в процессе построения модели рассматриваемой задачи заключается в определении всех возможных вариантов раскроя. Исходные соотношения для составления вариантов раскроя следующие:

 

Условие (25.46) означает, что длина отхода для любого варианта раскроя должна быть меньше, длины самой короткой заготовки (это является признаком полноценности варианта).

Рассмотрим пример. Снабженческо-сбытовая фирма получает от поставщиков прутки стального проката длиной 600 см. Согласно заявкам потребителей требуются заготовки трех видов в следующих количествах: 150 тыс. шт. длиной 250 см, 140 тыс. шт. длиной 190 см и 48 тыс. шт. длиной 100 см. Сформулируем экономико-математическую модель задачи оптимального раскроя с минимумом отходов. Составим таблицу возможных вариантов раскроя, при этом в первом блоке имеют место варианты раскроя, дающие все три вида заготовок, во втором - дающие заготовки второго и третьего вида, а в третьем – дающие заготовки только третьего вида.

Таблица 25.5

Возможные варианты раскроя

 

Блок	Номер варианта (j)	Количество заготовок (аij)	Остаток (сj)
l 1 = 250 см	l 2 = 190 см	l 3 = 100 см
I			- -		-
II		- - -		-
III		-	-		-

 

Пусть х ₁, x ₂, x ₃, х ₄, x ₅, х ₆, х ₇ – количества прутков, раскраиваемых по каждому варианту. Тогда целевая функция имеет вид:

 

Такое уравнение действительно при следующих условиях:

 

Задача о коммивояжере. Здесь требуется отыскать наилучший маршрут, с тем чтобы объехать все порученные коммивояжеру пункты и вернуться назад либо в кратчайший срок, либо с наименьшими затратами на проезд. В общем виде эту задачу можно сформулировать следующим образом.

Имеется п городов, занумерованных числами от 1 до п. Коммивояжер, выезжая из города 1, должен побывать в каждом городе ровно один раз и вернуться в исходный пункт. Известны расстояния между городами: с_ij (i, j = ; i ≠ j). Требуется найти самый короткий маршрут.

Введем переменные:

 

 

Требования однократного въезда и выезда из каждого города запишутся в виде:

 

 

Однако эти ограничения полностью не описывают допустимые маршруты, так как не исключают возможности разрыва пути, т.е. появления нескольких не связанных между собой подмаршрутов для части городов. Поэтому вводятся дополнительно переменных U_i, которые принимают только целые неотрицательные значения. Тогда можно записать еще (n – 1)² – (n – 1) ограничений:

 

 

Нетрудно показать, что ограничения (25.48) не исключают допустимый маршрут, но исключают возможность существования подмаршрутов.

Таким образом, задача о коммивояжере состоит в минимизации:

 

 

Это действительно при условиях (25.47), (25.48), где переменные x_ij, U_i принимают только неотрицательные целые значения.

Задача о размещении складов. Она является одной из оптимизационных задач исследования операций и решается обычно методами нелинейного программирования. Надо минимизировать общую сумму транспортных и складских расходов при следующих ограничениях:

а) с каждого предприятия должна быть отгружена вся продукция;

б) не может быть превышена емкость ни единого склада;

в) должны быть удовлетворены заявки всех потребителей.

В процессе решения задачи находится оптимальная по минимуму затрат трехчленная комбинация: предприятие – склад – потребитель. При некоторых условиях задача о размещении складов может сводиться к обычной транспортной задаче линейного программирования.

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