Транспортная задача

В этом примере необходимо определить оптимальный план перевозок про­дукции со складов в пункты реализации.

Предположим, что нужно перевести весь груз из трех складов в 2 пункт, причем весь груз должен быть перевезен во все пункты. В 1 пункт должно быть перевезено 45 единиц груза, в пункт 2 – 79. На складах груз размещен следующим образом: на складе 1 ­– 18 единиц, на складе 2 – 75 единиц, на складе 3 – 31 единица.

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

Таблица 4 – Стоимость перевозки единицы груза

В таблице 5 приведены переменные, которые обозначают объемы перевозок со складов в пункты назначения.

Таблица 5 – Обозначения для объемов перевозок

В данном примере целевая функция определяется как сумма затрат на перевозки:

J(cl, c2, c3, c4, c5, c6) = 17*c1 + 12*с2 + 9*с3 + 6*с4 + 13*c5 + 8*с6

Запишем уравнения для ограничений Тот факт, что все грузы перевезены записывается в виде трех уравнений:

cl + с4 = 18,

с2 + с5 = 75,

сЗ + с6 = 31.

Сумма грузов в каждом пункте дает еще два уравнения:

cl + с2 + с3 = 45,

с4 + с5 + с6 = 79.

Еще два ограничения: объемы грузов должны быть неотрицательными и целочисленными (предположим, что единицы продукции являются неделимыми).

Для решения задачи выполним следующие действия:

1. Введите в ячейку A1 формулу для целевой функции:

= 17*C1 + 12*С2 + 9*СЗ + 6*С4 + 13*C5 + 8*С6

2. Введите в ячейку A3 формулу для ограничения: =C1+C4.

3. Введите в ячейку А4 формулу для ограничения =С2+С5.

4. Введите в ячейку А5 формулу для ограничения =С3+С6.

5. Введите в ячейку А6 формулу для ограничения =С1+С2+С3.

6. Введите в ячейку А7 формулу для ограничения =С4+С5+С6.

7. Введем в ячейки С1:С6 начальные значения переменных (положим их нулевыми).

8. Выполним команду Сервис / Поиск решения. Появится окно «Поиск решения».

9. В поле Установить целевую функцию введем ячейку А1.

10. Установим переключатель в позицию Минимальное значение.

11. В поле ввода Изменяя ячейки укажем ячейки С1:С6.

Начнем вводить информацию в поле вода Ограничения. Нажмем кнопку Добавить. Появится окно диалога "Добавить ограничения". В ноле Ссылка на ячейки введем ячейку А3. В поле ввода Ограничение введем

= число 18. Аналогичную операцию проделаем с ячейками А4:А7.

12. Для ввода ограничений на неотрицательность переменных в окне диалога «Добавить ограничения» в поле Ссылка на ячейку введем С1:С6. В поле ввода Ограничение введем >= и число 0. Аналогичную операцию проделаем для ввода ограничений на целочисленность переменных, при этом в поле ввода Ограничение необходимо вводить цел (см. рисунок 8).

13. Нажмем кнопку Выполнить. Результаты решения показаны на рисунке 9.

Рисунок 8 ­– Ввод ограничений на условие целочисленности переменных

Рисунок 9 ­– Результат решения транспортной задачи

Задача о рюкзаке

В классических трудах по теории оптимизации достаточ­но часто выделяется отдельный класс задач, которым присвоено условное обозна­чение «задачи о рюкзаке»: турист со­бирается в поход и планирует взять с собой некоторое количество предметов (гру­зов) с различной степенью «полезности». Под «полезностью» конкретного пред­мета понимается совокупность его характеристик, определяющих эффективность использования этого предмета в походе, например, стоимость.

Для каждого предмета известен его вес.

Имеются и ограничение: выносливость туриста (какой вес он может нести).

Естественно, что общий вес всех предметов, которые целесообразно взять в по­ход, не превышает «грузоподъемность» туриста.

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

Очевидно, что обобщенная постановка задачи подразумевает самые различные транспортные средства (в этом качестве мы уже рассмотрели туриста, а могут быть грузовики, корабли, самолеты и прочее).

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

Первый (простой) пример такой задачи представлен на рабочем листе ЗадачаОРюкзаке (рисунок 10).

Рисунок 10 – Рабочий лист задачи о рюкзаке

В клетки таблицы заносятся следующие формулы:

I4 =H4*E4

I5 =H5*E5

I6 =H6*E6

I7 =H7*E7

J4 =H4*E8

J5 =H5*E9

J6 =H6*E10

J7 =H7*E11

I8 =СУММ(I4:I7)

J8 =СУММ(J4:J7)

Как видите, здесь речь идет о погрузке грузов четырех видов в самолет. При­мер является довольно простым, так как есть только два ограничения — по обще­му весу груза и по целочисленности количества предметов. В качестве критерия целесообразности загрузки предмета конкретного вида используется показатель под названием «эффективность» (измеряемый в некоторых единицах (баллах)).

Условия и ограничения задачи представлены на рисунке 11.

Рисунок 11 – Условия и ограничения задачи

Решение задачи представлено на рисунке 12.

Рисунок 12 – Решение задачи о рюкзаке

Рассмотрим задачу о рюкзаке с заданным и ограниченным множеством предметов. В данном случае предметы в рюкзак набираются из заданного набора предметов. Будет помещен предмет в рюкзак или нет обозначается специальным индексом, который может принимать значения 1 или 0 соответственно.

Лист задачи о рюкзаке с заданным множеством предметов приведен на рисунке 13.

Рисунок 13 – Лист задачи о рюкзаке с заданным множеством предметов

В клетки таблицы заносятся следующие формулы:

Q4

=B4*B6+C4*C6+D4*D6+E4*E6+F4*F6+G4*G6+H4*H6+I4*I6+J4*J6+K4*K6+L4*L6+M4*M6+N4*N6+O4*O6+P4*P6

Q5

=B5*B6+C5*C6+D5*D6+E5*E6+F5*F6+G5*G6+H5*H6+I5*I6+J5*J6+K5*K6+L5*L6+M5*M6+N5*N6+O5*O6+P5*P6

Условия и ограничения задачи представлены на рисунке 14.

Рисунок 14 – Условия задачи о рюкзаке с заданным множеством предметов

Решение задачи при принятых по умолчанию параметрах приведено на рисунке 15.

Рисунок 15 – Решение задачи о рюкзаке с заданным множеством предметов

Целевая функция в данной задаче имеет линейный вид. Для улучшения качества решения установим «Линейную модель» (см. рисунок 16).

Рисунок 16 – Окно параметров поиска решения с установленной линейной

моделью

При установке линейной модели решение несколько улучшилось (см. рисунок 17).

Рисунок 17 – Решение задачи о рюкзаке с заданным множеством предметов при линейной модели

В тоже время, истинное решение (полученное методом ветвей и границ [5, 6]) является еще более эффективным (см. рисунок 18).

Рисунок 18 – Глобальное решение задачи о рюкзаке с заданным множеством предметов

Список литературы

1. Excel для экономистов и менеджеров / А.Г.Дубина, С.С.Орлова, И.Ю.Шубина, А.В.Хромов. Спб.: Питер, 2004.

2. Долголаптев В.Г. Работа в Excel 7.0 для Windows 95 на примерах. М.: Бином, 1995.

3. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программирования. Минск: Вышэйшая школа, 2001.

4. Карманов В.Г. Математическое программирование. М.: Наука, 1975.

5. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

6. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск. Наука, 1978.

Содержание

Введение 3

1 Надстройка «Поиск решения» MS Excel 4

2 Задача об использовании сырья 8

3 Транспортная задача 12

4 Задача о рюкзаке 14

Список литературы 19

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