Реализация решения задачи в ЭТ Excel

Порядок выполнения работы.

Решить транспортную задачу, представленную в табличной форме:

	B 1	B 2	B 3
A 1
A 2
A 3

Реализация решения задачи (выполняется письменно).

Анализ транспортной задачи:

поставщики: общий запас: 40 + 80 + 20 = 140

потребители: общий спрос: 30 + 50 + 60 = 140

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

Замечание:

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

Для разрешимости транспортной задачи с открытой моделью необходимо преобразовывать ее в закрытую, путем ввода в первом случае фиктивного поставщика Am +1, где ; во втором случае фиктивного потребителя Bn +1, где .

Построение начального плана [2]:

o по правилу северо-западного угла

B 1 B 2 B 3       A 1                           A 2                           A 3

Порядок построения: Затраты:

o по правилу минимального элемента

B 1 B 2 B 3       A 1                           A 2                           A 3

Порядок построения: Затраты:

Реализация метода потенциалов для определения оптимального плана [3]:

Проверим начальный план на оптимальность:

B 1 B 2 B 3 u       A 1             -2       –   +   A 2               -6     +   –   A 3         -1     -4             v

Найдем потенциалы:

Определим оценки для свободных клеток:

Поскольку существуют свободные клетки с отрицательными оценками, то построенный план перевозок – не оптимальный.

Перейдем к нехудшему плану перевозок. Перспективными являются клетки (1; 3) и (3; 2). Наиболее потенциальной является клетка (1; 3). Строим для этой клетки цикл (по таблице):

Наибольшее количество груза в вершинах с отрицательным знаком: . В результате смещения l по циклу получаем новый план перевозок:

B 1 B 2 B 3 u       A 1         2                   A 2     8         -4     –   +   A 3     1   -1     -2     +   –   v

Затраты: Найдем потенциалы:

Определим оценки для свободных клеток:

Поскольку существуют свободные клетки с отрицательными оценками, то построенный план перевозок – не оптимальный.

Перейдем к нехудшему плану перевозок. Перспективной является клетка (3; 2). Строим для этой клетки цикл (по таблице):

Наибольшее количество груза в вершинах с отрицательным знаком: . В результате смещения l по циклу получаем новый план перевозок:

B 1 B 2 B 3 u       A 1                             A 2               -4             A 3               -3             v

Затраты: Найдем потенциалы:

Определим оценки для свободных клеток:

Поскольку отсутствуют свободные клетки с отрицательными оценками, то построенный план перевозок – оптимальный.

Ответ: .

Реализация решения задачи в ЭТ Excel.

1. Загрузить ЭТ Excel (через пункт меню Пуск или панель быстрого запуска).

2. Открыть файл (рабочую книгу) с именем ZLP.xls.

3. Переименовать лист в рабочей книге в ТЗ.

4. Выполнить решение задачи, используя инструмент Поиск решения, с формированием отчета по результатам.

1 шаг: сформировать таблицу, ввести значения и формулы

2 шаг: задать данные в полях надстройки «Поиск решения»

3 шаг: сформировать ответ и отчет по результатам

 

Варианты:

№ вар	Параметры транспортной задачи
a 1	a 2	a 3	b 1	b 2	b 3	c 11	c 12	c 13	c 21	c 22	c 23	c 31	c 32	c 33
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.

 

[1] Правило построения начального базисного плана перевозок определяет преподаватель

[2] Построение приведено на лекции.

[3] В качестве начального плана выбран план, построенный по правилу северно-западного угла. Решение с начальным планом, построенным по правилу минимального элемента, рассмотрено на лекции.