Referat.me

Название: Решение задачи о назначениях в программе Microsoft Excel

Вид работы: реферат

Рубрика: Информатика

Размер файла: 47.7 Kb

Скачать файл: referat.me-130416.docx

Краткое описание работы: Ответ на теоретический вопрос: Решение задачи о назначениях в программе Microsoft Excel Задача о назначениях – это так называемая распределительная задача, в которой на выполнение каждой работы требуется только один ресурс и каждый ресурс может быть использован только на одной работе. То есть ресурсы неделимы между работами, а работы неделимы между ресурсами.

Решение задачи о назначениях в программе Microsoft Excel

Ответ на теоретический вопрос:

Решение задачи о назначениях в программе Microsoft Excel

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

Задача

Для выполнения n работ могут быть использованы n работников. Эффективность i-го работника i = 1, …, n при выполнении им j-ой работы j = 1, …, n равна сij . Предполагается, что каждый работник может быть использован только на одной работе, а каждая работа может выполняться только одним работником. Определить, какую работу необходимо поручить каждому работнику, чтобы достичь максимальной эффективности по выполнению всех работ.

Математическая модель.

Введем переменную xij значение которой равно 1, если выполнение j-ой работы поручено i-му работнику, и равно 0, в противном случае. Тогда, поскольку на работе j может быть задействован только один работник, то справедливо равенство:

Так как один работник может выполнять только одну работу, то справедливо следующее равенство:

Целевая функция определяет эффективность всех работников при выполнении всех работ, которая должна быть максимальной

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

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

Имеется n городов. Расстояния между любой парой городов i и j известны и составляют cij . Коммивояжер выезжает из какого-либо города и должен посетить все города побывав в каждом только один раз и вернуться в исходный город. Ставится задача определить такую последовательность объезда городов, или маршрут, при которой суммарная длина маршрута была бы минимальной.

Математическая модель.

Определим булевы переменные задачи: xij = 1, если коммивояжер переезжает из города i в город j, и xij = 0, если коммивояжер не переезжает из города i в город j.

Тогда задача заключается в определении минимума целевой функции

при ограничениях

– только один въезд в город j,

– только один выезд из города i .

В задаче коммивояжера необходимо еще одно условие, а именно:

, i ≠ j, i, j = 2,…, n

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

3. Задача о доставке.

Фирма обслуживает m клиентов. Каждый день фирма поставляет своим клиентам товары на автомобилях (или на любом транспортном средстве). Существует n маршрутов доставки, каждый из которых позволяет обслужить определенное количество клиентов с использованием только одного транспортного средства. Каждый маршрут характеризуется определенными параметрами, которыми могут быть длина маршрута, стоимость расходуемого топлива на маршруте и т.д. Необходимо выбрать такое множество маршрутов, которое обеспечивало бы обслуживание каждого клиента и только один раз в день, при минимальных суммарных расходах.

Математическая модель.

Введем переменные xj с условиями: xj = 1, если выбран j-ый маршрут, и xj = 0 в противном случае, j = 1, … , n. Введем величины aij так, что aij = 1, если i-ый клиент обслуживается по маршруту j, и aij = 0 в противном случае i = 1, … , m, j = 1, … , n. Стоимость доставки по маршруту j обозначим как сj.

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

Ограничения

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

Решение задач средствами Excel.

Приведенные типы задач решаются средствами Excel также как и обычные транспортные задачи, за одним исключением: так как переменные по смыслу задачи могут принимать только двоичные значения 0 или 1, то в ограничениях, задаваемых в диалоговом окне Поиск решения, необходимо указать, что переменные имеют булевы значения.

Для этого необходимо нажать в окне Поиск решения кнопку Добавить (добавить ограничения) и в открывшемся диалоговом окне Добавление ограничения в левом поле занести ячейки с изменяемыми переменными, а в среднем поле, нажать на среднюю кнопку и выбрать в предложенных видах ограничений требование двоичности (рис. 1). Дальнейший алгоритм действий остается без изменений (см. Методические пособия к 1-ой и 2-ой Лабораторным работам).

Решение задачи коммивояжера на Excel.

Имеется 5 городов, расстояния Cij между которыми приведены в табл.

Номер города 1 2 3 4 5
1 9 8 4 10
2 6 4 5 7
3 5 3 6 2
4 1 7 2 8
5 2 4 5 2

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

Коммивояжер выезжая из города 1, должен посетить все города, побывав в каждом из них только по одному разу и вернуться в исходный город. Необходимо определить такой маршрут объезда городов, при которой длина маршрута будет минимальной.

2. Математическая модель

Переменные xij могут принимать значения равные либо 0, либо 1

– целевая функция

ограничения:

– условие въезда в город j только один раз

– условие выезда из города i только один раз

, где n = 5, т.е. , i ≠ j, i, j = 2,…, n .

Исходные данные в рабочей книге Excel приведены на рис. 2. Здесь же приведены формулы для вычисления ограничений и целевой функции.

На панели Поиск решения установить следующие параметры решения задачи:

Целевую ячейку – $B$10

Равной минимальному значению

Изменяя ячейки: $B$4:$F$8;$C$11:$F$11 – здесь заносятся не только ячейки, которые будут изменяться, и в которых будут занесены решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$11:$F$11, содержащие переменные ui , которые также являются изменяемыми.

Ограничения:

$B$21:$E$24≤3

$B$4:$F$8 = двоичное

$B$9:$F$9=1

$G$4:$G$8=1

$B$4=0

$C$5=0

$D$6=0

$E$7=0

$F$8=0

Параметры: линейная модель, неотрицательные значения, автоматическое масштабирование

После нажатия кнопки Выполнить на диалоговой панели Поиск решения. На рабочем листе Excel появляются результаты решения задачи.

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

1. Гельман В. Я. Решение математических задач средствами Excel. – СПб.: Питер, 2003;

2. Гарнаев А.. Excel, VBA, internet в экономике и финансах. – СПб.: БХВ – Петербург, 2003.

Похожие работы

  • Построение и анализ на чувствительность моделей задач линейного программирования

    Лабораторная работа №1 ПОСТРОЕНИЕ И АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: научиться определять оптимальный план производства (приобретения) продукции с учетом ограниченного обеспечения ресурсами различного вида; освоить методику и технологию поиска оптимального решения задач линейного программирования (ЗЛП) с помощью ЭВМ; приобрести практический опыт проведения анализа оптимального решения ЗЛП на чувствительность.

  • Использование диаграмм и графиков в табличном процессоре Microsoft Office Excel

    ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ПЕНЗЕНСКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ КАФЕДРА «ИНФОРМАЦИОННЫЕ КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ» Лабораторная работа №8

  • Создание макросов

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

  • Решение транспортных задач в Excel

    Министерство образования Российской Федерации Саратовский Государственный Технический Университет Кафедра «Организация перевозок и управление на транспорте»

  • Внедрение беспроводной связи для Ж Д GSM-R

    Курсовая работа по курсу «Управление проектами в области информационных систем» На тему: «Внедрение беспроводной связи для Ж/Д GSM-R» Планирование основных фаз и операций в проекте, определение длительности работ

  • Анализ области определения функции

    Постановка задачи Анализ области определения функции Рабочий лист Excel в режиме отображения значений Рабочий лист Excel в режиме отображения формул

  • Решение финансовых задач при помощи Microsoft Excel

    Лабораторная работа Вариант № 6 Задание: Управляющему банком были представлены 4 проекта, претендующие на получение кредита в банке. Ресурс банка в каждый период, потребности проектов и прибыль по ним приведены в таблице (тыс. долл.).

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

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

  • Лінійне програмування

    Транспортна задача Розв'язок задач лінійного програмування. Транспортна задача. Мета роботи: Набути навичок складання математичної моделі транспортної задачі та її реалізації з використанням табличного процесору Excel

  • Назначение и основные понятия электронных таблиц

    Назначение электронных таблиц Microsoft Excel — один из наиболее популярных пакетов для среды Windows , принадлежащий к классу так называемых табличных процессоров, или электронных таблиц. Но