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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть х ₁, 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 принимают только неотрицательные целые значения.

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

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

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

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

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

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

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: