Ответ на теоретический вопрос:
Решение задачи о назначениях в программе 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 появляются результаты решения задачи.
Список литературы
Гельман В. Я. Решение математических задач средствами Excel. – СПб.: Питер, 2003;
Гарнаев А.. Excel, VBA, internet в экономике и финансах. – СПб.: БХВ – Петербург, 2003.
Другие работы по теме:
Импорт таблиц EXCEL в текстовый документ WORD
Вопрос 12. Импорт таблиц EXCEL в текстовый документ WORD. Microsoft Excel – мощная программа для работы с электронными таблицами, являющаяся, также как и Word, частью пакета Microsoft Office. Обладая достаточно широкими возможностями и высокой степенью интеграции с другими приложениями Office и Windows вообще, Excel стала наиболее популярной программой среди людей, постоянно имеющих дело с огромными массивами чисел.
Венгерский метод в логистике
Содержание Введение 3 1 Задача о назначениях. Венгерский метод 4 1.1 Задача о назначениях 4 1.2 Венгерский метод решения задачи о назначениях 7 2 Решение задачи о назначениях с помощью венгерского метода 15
Microsoft Excel
Сегодня разработаны программные документы, с помощью которых рядовой пользователь очень быстро решает прикладные задачи, на решения таких задач в сфере экономии финансов и статистики у программистов прежних поколений уходили месяцы.
Электронные таблицы Excel
Overview Диаграмма1 Диаграмма3 Диаграмма2 Лист1 Sheet 1: Диаграмма1 Sheet 2: Диаграмма3 Sheet 3: Диаграмма2 Sheet 4: Лист1 остатки денежных средств на счетах клиентов
Microsoft Exel
ВОПРОСЫ К ЭКЗАМЕНУ ПО ИНФОРМАТИКЕ 2 семестр Табличные процессоры. Классификация. Табличный процессор Excel. Назначение. Основные приемы работы в Excel: ведение рабочей книги.
Створення та робота з таблицями у Microsoft Excel, Access
Характеристика методів створення таблиць і роботи з ними у програмі Microsoft Excel: розробка таблиці з прізвищами співробітників, розміщених у алфавітному порядку та сумами отримуваних ними заробітних плат. Створення таблиці в програмі Microsoft Access.
Решение финансовых задач при помощи Microsoft Excel
Выбор проектов из претендующих на получение кредита в банке. Учет ресурса банка для соответствующих периодов с целью максимизации прибыли. Оценка деятельности продавцов в различных торговых точках. Создние форм для ввода условий задач в Microsoft Excel.
Основи інформатики та застосування ЕОМ в психології
Користування програмами Microsoft Excel та Microsoft Access, створення таблиць за допомогою конструктора, занесення в них даних про студентів та їх успішність. Створення запитів до бази, які виводять інформацію; критерії відбору інформації для запиту.
Назначение и основные понятия электронных таблиц
Назначение электронных таблиц Microsoft Excel — один из наиболее популярных пакетов для среды Windows , принадлежащий к классу так называемых табличных процессоров, или электронных таблиц. Но
Создание макросов
Запись макроса При записи макроса все необходимые действия записываются программой записи макроса. Перемещение по ленте не включается в записанные шаги.
Microsoft X Essay Research Paper Microsoft XBoxThe
Microsoft X Essay, Research Paper Microsoft X-Box The Microsoft Corporation has changed the way we look at computers, but can they change anything else? Of course they can. Microsoft has expanded into the gaming world outside of the PC. They are now in competition with Nintendo, Sega, and other major gaming corporations.
Microsoft Essay Research Paper Microsoft has had
Microsoft Essay, Research Paper Microsoft has had a couple of though months since July last year, when Judge Thomas Jackson ordered the company to break up in two. However, since the beginning of this year things have just looked better for Microsoft.
Loophole Or A Conspiracy Essay Research Paper
Loophole Or A Conspiracy? Virus, Hmmm I am sure that you have heard this word before. I am not talking about the living virus like an influenza virus. I am talking about the computer virus. According to the New York Times, Microsoft, Compaq, and Hewlett Packards computers are at a great risk. I wonder why we the consumer, are in this position? I cannot come up with one straight answer.
Microsoft Essay Research Paper By running the
Microsoft Essay, Research Paper By running the Internet Microsoft could set up any programs that they wanted to. Also the software buyer would have to sue it because his system (computer) would only be
Information Methods Essay Research Paper The aim
Information Methods Essay, Research Paper The aim of this assignment was to show and explain the value and importance of information and the tools readily accessible to us as students. We were to investigate the individual components of Access, Excel, Word and Powerpoint, then to transform, manipulate and present the information we gathered.
MicrisoftA Modern Monopoly Essay Research Paper Many
Micrisoft-A Modern Monopoly Essay, Research Paper Many have asked the question of whether Microsoft has turned into a monopoly of the high technology and software industry. This question is an easy one to answer, yes it is. Over the years, Microsoft has used its wealth and influence over the software industry to pull away from the competition by threatening competitors of withdrawing contracts and software deals.
Microsoft As A Monopoly Essay Research Paper
My position today is proving to you, Your Honor, that Microsoft has used monopolistic practices and market power to foster a non-competitive climate. According to Webster, a monopoly is the exclusive control of a commodity or service in a given market.
Microsoft Essay Research Paper Microsoft the world
Microsoft Essay, Research Paper Microsoft, the world’s largest company by market value, is accused of acting monopolistic in the computer software industry. Microsoft provides for eighty percent of the computers used, operating system. The operating system is a basic program that loads or boots up your computer to make it perform.
Microsoft Monopoly Essay Research Paper By now
Microsoft Monopoly Essay, Research Paper By now everyone is familiar with the case U.S. vs. Microsoft. What is all this about? According to my two articles, Microsoft, the world’s leading software company, is being sued by the Justice Department joined by 19 states.
Bill Gates Essay Research Paper Bill GatesThe
Bill Gates Essay, Research Paper Bill Gates The Chairman and Chief Software Architect of Microsoft William Gates III was born in October 28, 1955. He lived in Seattle with his father who is a Seattle attorney, his mother who was a chairwoman of United Way International, and his two sisters.
Bill Gates Is The AntiChrist Essay Research
Paper Bill Gates is the Antichrist Ever since Microsoft was founded, Bill Gates has gained power over thepeople of the world by winning a monopoly in the computer-softwareindustry. From the assistance Microsoft gave in the development of thepersonal computer, to the virtual monopoly that Windows 95 now has onmost computers all over the world; Microsoft has controlled a majorportion of the computer industry.
Microsoft Antitrust Editorial Essay Research Paper Microsoft
Microsoft Antitrust Editorial Essay, Research Paper Microsoft: The Big Bully Stealing Your Lunch Money A monopoly, by definition, is a business or group that engages in unfair and often unethical business practices to control an industry and eliminate all competition that might lessen their profits.
Using Macros To Get The Most Out
Of Excel Essay, Research Paper As accounting professionals, accuracy in financial calculations and the integrity of the raw data are vital to producing useful information. Our clients prevail upon us to be more accurate and more thorough in less time. The tremendous advances in information technology are apparent across most industries.
Microsot Word 2000 Essay Research Paper Name
Microsot Word 2000 Essay, Research Paper Name and Type: -Microsot Word 2000 -Word Processor Producer/Maker: -Microsoft Corporation -The creator of the popular Windows operating system founded by Bill Gates.
Полевые измерений в TopconTools
Создаем новый проект рис 1 В созданном проекте подгружаем схему опорной геодезической сети рис 2 Далее импортируем необработанные данные полевых измерений рис 3
Гейтс (Gates) Уильям (Билл) Генри III
Гейтс (Gates) Уильям (Билл) Генри III (р. 28 октября 1955, Сиэтл, шт. Вашингтон), американский предприниматель и изобретатель в области электронно-вычислительной техники, председатель и CEO компании программного обеспечения Microsoft.
Табличний редактор Microsoft Excel
Теоретичні відомості 1.1. Табличний редактор Microsoft Excel Microsoft Excel – це складова частина пакето-прикладних програм Microsoft Office. Microsoft Excel – призначений для створення електронних таблиць і найбільшою перевагою є можливість досліджувати, аналізувати дані і виконувати обчислення.