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

history

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


В случае разумного числа комбинаций (до 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 куску.


Комментарии

Только для авторизованных пользователей

(только для авторизованных пользователей)

© Copyright 2013 - 2024 Excel2.ru. All Rights Reserved