Разрезка на мерные длины

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

В случае разумного числа комбинаций (до 100 тыс.) в MS EXCEL можно составить таблицу полного перебора вариантов разрезки (см. статью Комбинации элементов из нескольких множеств: Комбинаторика в MS EXCEL).

Задача

Завод выпускает провод партиями длиной 20 км. Клиенту требуются куски только 4-х размеров (все размеры поставлять не обязательно). Каким образом нужно разрезать 20 км, чтобы количество отходов было минимальным?

Решение

Подобная задача решена с помощью Поиска решения (см. статью Поиск решения MS EXCEL (1.7). Разрезка лент на части). Здесь решим задачу с помощью таблиц перебора.

Сначала рассчитаем, сколько в длине 20 км укладывается каждого из кусков (см. файл примера). Это можно сделать с помощью формулы =ЦЕЛОЕ($B$5/B8)

Затем подсчитаем общее количество комбинаций с помощью формулы массива =ПРОИЗВЕД(($B9:E9+1))

В вышеуказанной формуле +1 означает дополнительную комбинацию, когда размер не поставляется. Например, для Размера 4 общее количество вариантов разрезок будет равно 3, т.е. от 20 км можно отрезать 1 длину 7300м, или 2 по 7300, а можно не отрезать вообще, т.к. клиенту не обязательно, чтобы посталялись все размеры (см. условие задачи).

Получим вполне приемлемое количество комбинаций - 576. С помощью таблицы перебора всех комбинаций разрезки (см. статью Комбинации элементов из нескольких множеств: Комбинаторика в MS EXCEL) рассчитаем остаток для каждого варианта разрезки =$B$5-СУММПРОИЗВ($B$8:$E$8;B15:E15)

Минимальный остаток вычислим с помощью формулы массива =МИН(ЕСЛИ(F15:F590>=0;F15:F590;"")) (см. статью Максимальный и Минимальный по условию в MS EXCEL). Результат поместим в ячейку H10.

Номер варианта разрезки, при котором получается минимальный остаток, найдем с помощью формулы =ПОИСКПОЗ(H10;F15:F590;0) Результат поместим в ячейку H11.

Наконец, найдем сам вариант разрезки =ИНДЕКС(B15:B590;$H$11) Результат поместим в строку 11.

В файле примера рассмотрена еще одна задача:

Завод выпускает провоку партиями длиной 70 км. Клиенту требуются куски только 5-и размеров. Клиенту требуются куски только определенных размеров (всего размеров 5, обязательно, чтобы в поставке были все размеры). Каким образом нужно разрезать провод длиной 70 км, чтобы количество немерных остатков было минимальным.

В этом случае клиенту требуется, чтобы в поставке были представлены все размеры. Решение практически аналогично, но необходимо контролировать, чтобы 70 км хватило на сумму длин всех размеров, взятых по 1 куску.

 

Связанные статьи

Похожие задачи
Прочитайте другие статьи, решающие похожие задачи в MS Excel. Это позволит Вам решать широкий класс подобных задач.
Средняя: 5 (2 оценок)

Комментарии

MCH

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

Creator

Согласен на все 100%. Но, все же:

  • Предложенный в статье подход очень удобен (для не очень большого количества вариантов разрезок). Не нужно писать программы и вообще вникать в тему динамического программирования.
  • Цель нашего сайта показать возможности EXCEL без программирования на VBA.