Markets-Web.ru

Пусть х1, x2, x3, х4, x5, х6, х7 – количества прутков, раскраиваемых по каждому варианту. Тогда целевая функция имеет вид:

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

Задача о коммивояжере.

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

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

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

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

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

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

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

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

Задача о размещении складов.

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

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

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

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

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

Задача о ранце (или о рюкзаке).

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