Решение. Построим математическую модель данной задачи

Теоретически это уменьшение равно (q умножить на соответствующее превышение), т.е. те же 360 (произведение 90 на 4).

Рассчитаем новую систему потенциалов.

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

Имеем 6 уравнений и 7 неизвестных. Значение одной из неизвестных величин (любой!) можно задать произвольным образом (любое число). Положим U₃ равным 0. Тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=8_, V₂=7_, V₃=4_, V₄=6 _.

Припишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строку V_j (рис.3.6).

Вычислим значения невязок для всех клеток без перевозок по формуле (3.7). Запишем их в правый верхний угол каждой клетки (жирный курсив). В одной клетке (3,1) наблюдается нарушение (невязка равна 3, т.е. больше нуля). Построим замкнутый цикл с началом в этой клетке. В качестве остальных вершин выберем клетки (1,1),(1,2) и (3,2). Пронумеруем клетки (рис. 3.6).

Нечетные вершины (3,1) и (1,2) образуют положительную полуцепь. Четные вершины (1,1) и (3,2) образуют отрицательную полуцепь. Величина q = min{30;140}=30.

Вычислим новые значения для узлов контура.

В четных вершинах значения уменьшается на q=30: в клетке (1,1) значение перевозки станет равным 30-q=0; в клетке (3,2) - равным 140 - q=140-30=110.

В нечетных вершинах значения увеличатся на q: в клетке (3,1) значение станет равным 0+q=0+30=30, а в клетке (1,2) - 60+q=60+30=90.

Получим новое опорное решение (рис.3.7).

Рис.3.7

Вычислим суммарную стоимость перевозок для вновь полученного опорного плана:

.

Уменьшение стоимости перевозок по сравнению с предыдущим планом составило F₁ -F₂ = 2340 – 2250 = 90.

Теоретически это уменьшение равно (q умножить на соответствующее превышение), т.е. те же 90 (произведение 30 на 3).

Рассчитаем очередную систему потенциалов для полученного опорного решения. Для определения ; имеем следующую систему уравнений:

Имеем 6 уравнений и 7 неизвестных. Положим U₃ = 0, тогда остальные величины будут равны

U₁=1_, U₂=3_, V₁=5_, V₂=7_, V₃=4_, V₄=6_.

Запишем значения потенциалов соответствующим строкам и столбцам в столбец U_i и строку V_j (рис. 3.6).

Вычислим значения невязок для всех клеток без перевозок по формуле (3.7). Все невязки неположительны, следовательно, оптимальное решение найдено.

3.2.3. Решение транспортной задачи в MS Excel

Решим данную задачу в MS Excel, используя надстройку «Поиск решения». Схема решения транспортной задачи совпадает с общей схемой решения любой задачи линейного программирования (например, задачи об оптимальном распределении ресурсов).

Заполним лист MS MS Excel, как показано на рисунке 3.8. На рисунке 3.9. показан тот же лист в режиме отображения формул.

 

Рис.3.8.

 

Рис.3.9.

Результат решения приводится на рис.3.10.

Рис.3.10

Оптимальные объемы перевозок содержатся в интервале ячеек В13:Е15. Заметим, что результаты полностью совпадают с результатами, полученными ранее методом потенциалов.

Задание

Каждый вариант состоит из одного примера.

Имеется четыре карьера, производящих строительные материалы, и четыре потребителя сырья строительных материалов. Известны объемы производства на каждом карьере, потребности в их продукции каждого из потребителей, а также стоимость перевозки 1 т продукции с i -го карьера к j -му потребителю.

Определить, при каких объемах грузоперевозок от i -го поставщика к j -му потребителю суммарная стоимость перевозок будет минимальной.

1. Решить задачу средствами MS Excel (Надстройка “Поиск решения”).
2. Решить задачу аналитически.

Отчет должен содержать:

1). Условие задачи

2). Постановку задачи. Формулировку задачи линейного программирования.

3). Решение задачи на MS Excel с использованием надстройки «Поиск решения»

4). Аналитическое решение транспортной задачи:

· определение исходного опорного решения;

· построение оптимального решения методом потенциалов.

Варианты заданий

Вариант 1

Поставщик	Потребители	Запасы
Потребность

Вариант 2

Поставщик	Потребители	Запасы
Потребность

Вариант 3

Поставщик	Потребители	Запасы
Потребность

Вариант 4

Поставщик	Потребители	Запасы
Потребность

Вариант 5

Поставщик	Потребители	Запасы
Потребность

Вариант 6

Поставщик	Потребители	Запасы
Потребность

Вариант 7

Поставщик	Потребители	Запасы
Потребность

Вариант 8

Поставщик	Потребители	Запасы
Потребность

Вариант 9

Поставщик	Потребители	Запасы
Потребность

Вариант 10

Поставщик	Потребители	Запасы
Потребность

Вариант 11

Поставщик	Потребители	Запасы
Потребность

Вариант 12

Поставщик	Потребители	Запасы
Потребность

Вариант 13

Поставщик	Потребители	Запасы
Потребность

Вариант 14

Поставщик	Потребители	Запасы
Потребность

Вариант 15

Поставщик	Потребители	Запасы
Потребность

 

ЛАБОРАТОРНАЯ РАБОТА 4

4. ЗАДАЧА О НАЗНАЧЕНИЯХ

Цель работы: изучить постановку задачи о назначениях; освоить венгерский метод.

4.1. Постановка задачи. основные формулы

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

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

Построим математическую модель этой задачи. Сопоставим каждому из возможных вариантов распределения работников по работам набор значений неизвестных , относительно которых условимся, что , если в данном варианте i -й работник назначается на j -ю работу, и , если i -й работник назначается не на j -ю работу.

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

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

Таким образом, математическая модель задачи о назначениях будет такой:

	(4.1)
	(4.2)
	(4.3)

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

Эта задача имеет простую геометрическую интерпретацию, показанную на рис.(4.1). На нем изображен граф, у которого вершины слева обозначают работников, а вершины справа изображают работы. Вершины соединены ребрами с указанием их веса, при этом вес равен стоимости соответствующей работы.

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

Паросочетанием неориентированного графа G называется подмножество M его ребер E, выбранное так, что никакие два ребра из M не являются смежными, т.е. не имеют общей вершины. В терминах нашей задачи синонимом этому будет «назначение», чтобы каждый задействованный работник взял на себя отдельную работу. И не получилось такого, что два работника выполняет одну работу, или один работник отвечал за две работы.

Рис.4.1

Она является частным случаем задачи нахождения совершенного паросочетания (см.приложение).

Решение этой задачи может быть получено венгерским методом. Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кёнига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry). Основную суть метода рассмотрим на примере.