48112 (Постановка и решение транспортной параметрической задачи), страница 2

2016-07-30СтудИзба

Описание файла

Документ из архива "Постановка и решение транспортной параметрической задачи", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "48112"

Текст 2 страницы из документа "48112"

Значения aij и Bij определяются из условия

где определяются из систем уравнений

Значения k находятся в пределах k1≤k≤k2:


если существует хотя бы одно Bij>0;


если все Bij≥0

если существует хотя бы одно Bij>0;

если все Bij≤0.

Алгоритм решения.

  1. Задачу решаем при конкретном значении параметра k=δ до получения оптимального решения.

  2. Определяем aij и Bij.

  3. Вычисляем значение параметра k.

  4. Если k>δ, производим перераспределение поставок и получаем новое оптимальное решение. Если k = δ, то процесс решения окончен [1].

3 Метод решения задачи об оптимальных перевозках средствами Ms Excel

Нахождение оптимального плана перевозок с применением компьютерной программы Ms Excel осуществляется посредством функции "Поиск решения".

Схема выполнения:

1. Для удобства расчетов необходимо отдельно создать матрицу, отображающую стоимость перевозок (Cij) (рис 3.1.), а также матрицу, которая должна будет отображать искомый план перевозок (рис. 3.2.).

Рис. 3.1. Фрагмент окна программы Ms Excel: Модель таблицы «Стоимость перевозок».

2. В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.

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

Рис. 3.2. Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок».

4. В ячейке целевой функции ввести формулу, высчитывающую сумму произведений элементов матрицы "Стоимость перевозок" и соответствующих элементов матрицы "План перевозок".

5. В диалоговом окне функции "Поиск решения" установить необходимые ограничения, в целевой ячейке указать адрес ячейки с формулой целевой функции и установить ее равной минимальному значению, в качестве изменяемых ячеек выбрать диапазон всех элементов матрицы "План перевозок". Ограничения в "Поиске решений" заключаются в необходимости равенства запасов (потребностей), в матрице "План перевозок" соответствующим запасам и потребностям, указанным в матрице "Стоимость перевозок". Также все элементы матрицы "План перевозок" должны быть неотрицательными и целочисленными.

6. В диалоговом окне "Параметры поиска решения" установить параметр "Линейная модель" и число итераций, равное 100.

7. Выполнить функцию "Поиск решения" нажатием на кнопку "Выполнить". В качестве отчета по результатам выбрать необходимый пункт в списке "Тип отчета" диалогового окна «Результаты поиска решения».

После выполнения вышеуказанных действий при условии, что задача имеет решение, в матрице «План перевозок» запишется оптимальное решение задачи, т.е. оптимальный план перевозок с указанием объемов поставок в каждой ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.

4. Решение параметрической транспортной задачи

4.1 Постановка параметрической транспортной задачи

Имеется четыре поставщика однородного груза с объемами поставок 100, 70, 70, 20 т. и три потребителя с объемами потребления 120, 80, 60 т. Стоимость транспортных расходов задана матрицей

причем стоимость перевозки груза от четвертого поставщика до третьего потребителя изменяется в диапазоне 0≤k≤9.

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

Изобразим матричную запись задачи (табл. 4.1.1)

Табл. 4.1.1. Матричная запись задачи

Bj

Ai

B1

B2

B3

120

80

60

A1

100

2

4

2

X11

X12

X13

A2

70

5

5

6

X21

X22

X23

A3

70

4

7

3

X31

X32

X33

A4

20

6

8

1+k

X41

X42

X43

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

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

.

где Xij – объем поставок груза,

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

Xij≥0,

Подробные ограничения по потребностям и запасам каждого потребителя и поставщика соответственно отражены в Таблице 4.2.1.

Табл. 4.2.1. Ограничения по потребностям и запасам

По потребностям

По запасам

B1

X11+X21+X31+X41=120

A1

X11+X12+X13=100

B2

X12+X22+X32+X42=80

A2

X21+X22+X23=70

B3

X13+X23+X33+X43=60

A3

X31+X32+X33=70

A4

X41+X42+X43=70

4.3 Решение задачи аналитическим методом

Полагая k=0, по известному алгоритму составим опорное решение методом Фогеля. Полученный опорный план перевозок и алгоритм выполнения с нахождением минимальных разностей стоимостей перевозок (Cij) в каждом столбце и строке изображен на рисунке 4.3.1.

Рис. 4.3.1. Составление первого опорного решения задачи по методу Фогеля

Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В3 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.1.

Решение, полученное при k=0, является оптимальным для всех значений параметра k, удовлетворяющих условию .

Из условия для свободных клеток найдем:

13 = v3 + u1 - c'13 = -1 + 2 - 2 = -1

21 = v1 + u2 - c'21 = 0 + 3 - 5 = -2

23 = v3 + u2 - c'23 = -1 + 3 - 6 = -4

32 = v2 + u3 - c'32 = 2 + 4 - 7 = -1

41 = v1 + u4 - c'41 = 0 + 2+k - 6 = -4 + k

42 = v2 + u4 - c'42 = 2 + 2+k - 8 = -4 + k

Табл. 4.3.1. Проверка первого опорного решения на оптимальность методом потенциалов

заполненные

незаполненные

vi + uj = cij

значения

vi + uj ≤ cij

условие

А1В1

v1+u1=2

v1=0, u1=2

А1В3

v3+u1<=2

соблюдается

А1В2

v2+u1=4

v2=2

А2В1

v1+u2<=5

соблюдается

A2B2

v2+u2=5

u2=3

А2В3

v3+u2<=6

соблюдается

A3B1

v1+u3=4

u3=4

А3В2

v2+u3<=7

соблюдается

A3B3

v3+u3=3

v3= -1

A4B1

v1+u4<=6

соблюдается

A4B3

v3+u4=1+k

u4=2+k

A4B2

v2+u4<=8

соблюдается

Определение значений k1 и k2:

k1 = max(-aij/Bij) = т.к. все Bij ≥ 0

k2 = min(-aij/Bij) = (-a41/B41; -a42/B42) = min(4;4) = 4. Все Bij > 0.

Так как по условию задачи k≥0, то оптимальное решение сохраняется при 0≥k≥4.

При этом минимальная стоимость транспортных расходов составляет:

F(X1)min = 20*(1+k) + 40*3 + 30*4 + 90*2 + 10*4 + 70*5 = 830 + 20k

Таким образом, при , F(X1)min = 830 + 20k и

.

Чтобы получить оптимальное решение при k≥4 перераспределим поставки товаров в клетку (4,1), где k2=4. Вновь полученное распределение с учетом изменения стоимости перевозки в ячейке A4B3 (k=4) представлено на рисунке 4.3.2.

Рис. 4.3.2. Составление второго опорного решения задачи по методу Фогеля

Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А4В1 - А3В3 - А3В1 - А1В1 - А1В2 - A2B2.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия vi + uj = cij для занятых клеток и проверка условия vi + uj ≤ cij для незанятых приведены в таблице 4.3.2.

Табл. 4.3.2 Проверка второго опорного решения на оптимальность методом потенциалов

заполненные

незаполненные

vi + uj = cij

значения

vi + uj ≤ cij

условие

А1В1

v1+u1=2

v1=0, u1=2

А1В3

v3+u1<=2

соблюдается

А1В2

v2+u1=4

v2=2

А2В1

v1+u2<=5

соблюдается

A2B2

v2+u2=5

u2=3

А2В3

v3+u2<=6

соблюдается

A3B1

v1+u3=4

u3=4

А3В2

v2+u3<=7

соблюдается

A3B3

v3+u3=3

v3= -1

A4B2

v2+u4<=8

соблюдается

A4B1

v1+u4=6

u4=6

A4B3

v3+u4<=1+k

соблюдается

Решение, полученное при k=4, является оптимальным для всех значений параметра k, удовлетворяющих условию .

Из условия для свободных клеток найдем:

13 = a3 + b1 - C'13 = -1 + 2 - 2 = -1

21 = a1 + b2 - C'21 = 0 + 3 - 5 = -2

23 = a3 + b2 - C'23 = -1 + 3 - 6 = -4

32 = a2 + b3 - C'32 = 2 + 4 - 7 = -1

42 = a2 + b4 - C'42 = 2 + 6 - 8 = 0

43 = a3 + b4 - (C'43 + С''43) = -1 + 6 - (1+k) = 4-k

Определение значений k1 и k2

k1 = max(-aij/Bij) = -a43/B43 = 4. Все Bij < 0

k2 = min(-aij/Bij) = т.к. все Bij ≤ 0

Так как по условию задачи k ≤ 9, то оптимальное решение сохраняется при 4≥k≥9.

При этом минимальная стоимость транспортных расходов составит:

F(X2)min = 20*6 + 60*3 + 10*4 + 90*2 + 10*4 + 70*5 = 910

Таким образом, при F(X2)min = 910 и

.

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

Создадим в окне программы Ms Excel две матрицы «План перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис 4.4.1). Также нужно указать ячейку содержащую изменяемый параметр k. При этом в клетке A4B3 матрицы «Стоимость перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от параметра k: L7=1+L9.

Рис. 4.4.1. Фрагмент окна программы Ms Excel: Матрицы «План перевозок» и «Стоимость перевозок» с изменяемым тарифом C43.

В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ(C4:E4), C3=СУММ(С4:С7).

В ячейку целевой функции (N7) введем =СУММПРОИЗВ(C4:E7;J4:L7).

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

В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения и ссылки на необходимые ячейки (рис. 4.4.2). Также необходимо в ограничениях указать пределы изменения параметра k, т.е. 0≤k≤9.

Рис. 4.4.2. Диалоговое окно «Поиск решения»

В диалоговом окне «Параметры поиска решения» установить необходимые параметры (рис. 4.4.3).

Рис. 4.4.3. Диалоговое окно «Параметры поиска решения»

После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» (рис. 4.4.5) нажать «Сохранить сценарий…» и в появившемся диалоговом окне «Сохранение сценария» задать имя данному сценарию и нажать «ОК» (рис. 4.4.4.).

Рис. 4.4.4. Диалоговое окно «Сохранение сценария»

После сохранения сценария в диалоговом окне «Результаты поиска решения» выделить необходимые типы отчетов и нажать «OK» (рис. 4.4.5.).

Рис. 4.4.5. Диалоговое окно «Результаты поиска решений

После выполнения всех операций в матрице «План перевозок» получим оптимальный план перевозок при k=0 (рис. 4.4.6.).

Рис. 4.4.6. Фрагмент окна программы Ms Excel: Результат поиска решения при k=0.

Полученное значение целевой функции F(x1)min=830.

Теперь аналогичным способом найдем оптимальный план перевозок при k=1. Проведя повторный расчет, получим новый план перевозок и значение целевой функции (рис 4.4.7.).

Рис. 4.4.7. Фрагмент окна программы Ms Excel: Результат поиска решения при k=1

Полученное значение целевой функции F(x2)min = 850.

Как видно из рисунков 4.4.5. и 4.4.6 планы перевозок в обоих случаях (k=0, k=1) одинаковы. После дальнейших расчетов при всех остальных значениях параметра k обнаружим, что при план перевозок остается неизменным, изменяется лишь значение целевой функции. При значении параметра «Поиск решения» выдает другой план перевозок, и значение целевой функции на данном промежутке остается неизменным F(x)min = 910. Полученный план перевозок при значении k=4 изображен на рисунке 4.4.8.

Рис. 4.4.8. Фрагмент окна программы Ms Excel: Результат поиска решения при k=4

Значения целевой функции, соответствующие параметру k в каждой итерации представлены в таблице 4.4.1.

Из представленных в таблице 4.4.1 данных можно вывести определенную закономерность изменения значения целевой функции на промежутке :

F(x1)min = 830, (k=0);

F(x2)min = F(x1)min +20 = 830+20, (k=1);

F(x3)min = F(x2)min +20 = 830 + 20*2 = 870, (k=2).

Следуя по той же цепочке, найдем:

F(x4)min = 830 + 20*3, (k=3).

F(x5)min = 830 + 20*4, (k=4).

Исходя из подобной логики можно представить F(x1)min = 830 + 20*0.

Отсюда можно вывести формулу, отображающую закономерность изменения значения целевой функции при :

.

Для значений значение функции постоянно F(x)=910.

Таблица 4.4.1. Значения целевой функции в каждой итерации

номер итерации i

значение параметра ki

значение функции F(xi)min

1

0

830

2

1

850

3

2

870

4

3

890

5

4

910

6

5

910

7

6

910

8

7

910

9

8

910

10

9

910

Команда «Сервис → Сценарии» открывает диалоговое окно «Диспетчер сценариев», которое отображает сохраненные сценарии каждой итерации нахождения оптимального плана перевозок (рис 4.4.9.).

Рис. 4.4.9. Диалоговое окно «Диспетчер сценариев»

С помощью «Диспетчера сценариев» можно просмотреть план перевозок и значение целевой функции, получаемые при каждом значении параметра k. Также можно просмотреть отчет, отображающий значения изменяемых ячеек в каждой из итераций.

Заключение

Ответ.

, , F(X1)min = 830 + 20k.

, , F(X2)min = 910.

Представленная в данной курсовой работе параметрическая транспортная задача решена двумя способами: аналитическим методом Фогеля и средствами компьютерной программы Ms Excel. Оба предложенных метода дают одинаковое решение и определяют оптимальный план перевозок товара и минимальную стоимость всех перевозок для каждого из промежутков диапазона изменения параметра, определяющего тариф одной из перевозок.

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

Библиографический список

  1. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом анализе: Учебник. – 3-е изд., исп. – М.: Дело, 2002. – 688 с.

  2. И.Л. Акулич. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. - М.: Высшая школа, 1986 г, 319 с.

  3. Т.Н. Павлова, О.А. Ракова. Линейное программирование. Учебное пособие. - Димитровград, 2002 г.

  4. Т.Н. Павлова, О.А. Ракова. Решение задач линейного программирования средствами Excel. Учебное пособие. - Димитровград, 2002 г.

  5. В.И. Ермаков. Сборник задач по высшей математике для экономистов. - М.: Издательство Инфра, 2001 г, 574 с.

Свежие статьи
Популярно сейчас
А знаете ли Вы, что из года в год задания практически не меняются? Математика, преподаваемая в учебных заведениях, никак не менялась минимум 30 лет. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4121
Авторов
на СтудИзбе
667
Средний доход
с одного платного файла
Обучение Подробнее