Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Содержание

• 1. Постановка задачи
• 2. Описание алгоритма решения задачи
• 3. Решение задачи вручную
• 4. Решение в программе TORA
• 5. Решение в программе MS Excel
• 6. Разработка программы для решения задачи в общем виде (Delphi)
• Выводы
• Список используемой литературы
• 1. Постановка задачи

1. Выбрать и обосновать наиболее эффективный метод решения задачи.

2. Разработать алгоритм и программу для решения задачи в общем виде.

3. Проверить правильность алгоритма на предлагаемой задаче.

4. Задача:

Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000,2000,1600 т каждому. Расстояние от элеватора до хлебозаводов указано в следующей таблице:

Элеваторы	Хлебозаводы
	1	2	3
1 2	20 60	30 20	50 40

Затраты на перевозку 1 т продукта на 1 км составляют 25 д.е.

Спланируйте перевозки зерна из условия минимизации транспортных расходов.

2. Описание алгоритма решения задачи

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

1. Проверить на сбалансированность.

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

Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. то необходимо ввести фиктивного (n+1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза;

1. Определить начальное решение.

Найдем начальное решение методом наименьшего элемента, который позволяет построить опорное решение, достаточно близко к оптимальному.

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

Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимостей транспортной задачи , i=1,2,…,m; j=1,2…,n. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют также. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично поступают с потребителем;

2. Проверить полученный опорный план на невырожденность.

План называется вырожденным, если количество базисных клеток в нем меньше, чем m + n - 1.Опорный план - невырожден, если число ненулевых перевозок равно n+m-1, поэтому и первоначальный план также должен удовлетворять этому требованию;

3. Найти потенциалы опорного решения.

Метод потенциалов предназначен для окончательной оптимизации решения транспортной задачи.

Если допустимое решение , i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков i=1,2,…,m и потребителей j=1,2,…,n, удовлетворяющее следующим образом:

Группа равенств (2.1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных i=1,2,…,m и j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств (2.2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:

(2.3)

Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

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

Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k) таблицы, соответствующую . Если , то решение оптимальное. Если же , то для соответствующей клетки (l,k) строят цикл и улучшаю решение, перераспределяют груз по этому циклу;

4. Обоснование результата

3. Решение задачи вручную

1 Проверим на сбалансированность.

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

Элеватор	Хлебозавод	Запасы зерна
	1	2	3
1	20	30	50	4200
2	60	20	40	1200
Потребность в зерне	1000	2000	1600

Запасы зерна на элеваторах :

? A_i = 4200 + 1200 = 5400

Потребность в зерне хлебозаводов:

? B_i = 1000 + 2000 + 1600 = 4600

Так как ? A_i > ? B_i, то вводим «Фиктивный» пункт потребления - хлебозавод №4 с потребностью в зерне :

B4 = ?A_i - ?B_i = 5400 - 4600 = 800 т. и с нулевыми расстояниями до элеваторов.

Занесем исходные данные в распределительную таблицу.

	B1	B2	B3	B4	?Ai
A1	20	30	50	0	4200
A2	60	20	40	0	1200
? Bi	1000	2000	1600	800	5400

2 Отыщем начальное решение. Методом минимального элемента.

Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

	B1	B2	B3	B4	? Ai
A1	20 (1000)	30 (800)	50 (1600)	0 (800)	4200
A2	60	20 (1200)	40	0	1200
? Bi	1000	2000	1600	800	5400

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

3 Проверим полученный опорный план на невырожденность.

Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.

4 Найдем потенциалы опорного решения.

U_i, V_i. по занятым клеткам таблицы, в которых U_i + V_i = С_ij, полагая, что u₁ = 0;

Получим v₁=20; v₂=30; v₃=50; v₄=0; u₂= -10



Ui Vi	v1=20	v2=30	v3=50	v4=0
u1=0	20 (1000)	30 (800)	50 (1600)	0 (800)
u2= -10	60	20 (1200)	40	0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию U_i + V_i <= С_ij.

При этом грузооборот составит:

Q = 20*1000 + 30*800 + 50*1600 + 0*800 + 20*1200 = 148000 тон/км.

5 Обоснование результата

Так как затраты на перевозку 1 т продукта на 1 км составляют 25 д.е., то денежные затраты составляют:

S = 148000*25 = 3700000 д.е.

4. Решение в программе TORA

Программа TORA реализует решение задач линейного программирования.

В данной курсовой работе программа TORA используется для решения транспортной задачи методом наименьшего элемента.

Чтобы решить данную транспортную задачу, запускаем программу Tora.exe, в главном меню программы выбираем Transportation model (Транспортная модель).

Далее, выбираем необходимое количество ограничений и переменных (см. рисунок 1).



Рис.1 Заполнение переменных

Теперь нужно ввести все значения переменных в созданную таблицу (см. рисунок 2).

транспортный задача алгоритм



Рис.2 Заполнение таблицы

Когда данные будут введены, нажимаем кнопку «SOLVE Menu» и выбираем метод Solve Problem => Iterations => Least-Cost starting solution (Метод наименьшего элемента) с помощью которого необходимо решить задачу.

Далее, появиться оптимальное решение транспортной задачи (см. рисунок 3).



Рис.3 Оптимальное решение

Как видно из решения программы грузооборот составит:

Q = 148000 тон/км.

Рассчитаем перевозки зерна из условия минимизации транспортных расходов.

Так как затраты на перевозку 1 т продукта на 1 км составляют 25 д.е., то денежные затраты составляют:

S = 148000*25 = 3700000 д.е.

5. Решение в программе MS Excel

Мощным средством анализа данных MS Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Для расчета заданного значения применяются различные математические методы поиска. Программа Поиск решений (в оригинале Excel Solver) - дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных задач оптимизации. Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:

- количество неизвестных (decision variable) - 200;

- количество формульных ограничений (explicit constraint) на неизвестные - 100;

- количество предельных условий (simple constraint) на неизвестные - 400.

Для решения данной транспортной задачи будем проводить MSExcel 2007. Запустим файл «TZ.xlsm». После запуска файла нужно включить макросы «Параметры» => «Включить содержимое» (см. рисунок 4).

Рис.4 Включение макросов

По умолчанию в MSExcel 2007 надстройка «Поиск решения» отключена. Чтобы активизировать ее необходимо перейти на вкладку «Пуск », нажать кнопку «Параметры Ecxel» => «Надстройки» и установить флажок рядом с пунктом «Поиск решения». Нажать «ОК» (см. рисунок 5).

Рис.5 Надстройки «Поиск решения»

Далее переходим к вводу данных задачи.

В ячейки «E7-G8» вводим расстояния до хлебозаводов, в ячейки «E12-G12» вводим потребности хлебозаводов, в «I7;I8» вводим запасы в элеваторах и в ячейку «F26» вписывается значение затрат на 1 единицу. В ячейки «H7» и «H8» вставляем нули, так как данная задача несбалансированна и запасы превышают потребности и вводится фиктивный потребитель, ячейка «H12» считается автоматически, как только будут заполнены ячейки с потребностями и запасами «=(I7+I8)-(E12+F12+G12)» (см. рисунок 6).



Рис.6 Ввод данных

На вкладке «Данные» нажимаем надстройку «Поиск решения» (см. рисунок 7).

Устанавливаем целевую ячейку «F28», так как нам нужно найти минимальные затраты ставим галочку на «Минимальное значение»

Расчеты и изменения будут происходить в ячейках «E18-H19», поэтому и указываем эти ячейки в графе «Изменения ячейки»

Необходимо указать ограничения:

В ячейках «E18-H19 »введем параметр > 0, так как оптимальный план не может иметь отрицательных значений.

«I18;I19» <= «I7;I8»,

«E24;H24» = «E12;H12».

Рис.7 Параметры функции «Поиск решения»

После того, как выставлены все ограничения, нажимаем на кнопку «Выполнить». Программа рассчитает оптимальный грузооборот и выведет его в ячейку «F28». А в ячейку «H28» будут минимальные расходы на грузоперевозки (см. рисунок 8).

Рис.8 Результат расчетов

Если необходимо изменить исходные данные и пересчитать целевую функцию - можно воспользоваться макросом для поиска решения, нажав на сочетание клавиш Alt+F8 выполнить «Makros1».

Как видно из ячейки «F28» грузооборот составит:

Q = 148000 тон/км.

А в ячейке «H28» рассчитаются денежные затраты :

S = 3700000 д.е.

6. Разработка программы для решения задачи в общем виде (Delphi)

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

Инструкция пользователю.

Назначение.

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

Программные и аппаратные требования.

Компьютер и процессор	Частота не ниже 500 МГц
Память	ОЗУ не менее 256 МБ
Место на жестком диске	2 ГБ..
Экран	Разрешение не менее 1024x768 точек
Операционная система	Microsoft Windows XP, Windows 7, Windows 8,Server 2003, Server 2008) или более поздняя версия
Программы	Microsoft Office 2007, 2010.

Установка программы.

Необходимо скопировать файлы «TZ.xlsm» и «Var16.exe» в одну папку.

Для корректной работы программы нужно запустить «TZ.xlsm». По умолчанию в MSExcel 2007 надстройка «Поиск решения» отключена. Чтобы активизировать ее необходимо перейти на вкладку «Пуск », нажать кнопку «Параметры Ecxel» => «Надстройки» и установить флажок рядом с пунктом «Поиск решения». Нажать «ОК» (см. рисунок 9).

Рис.9 Надстройки «Поиск решения»

После чего перейти на вкладку «основные» активировать для показа на ленте вкладку «Разработчик» (см. рисунок 10).

Рис.10 Надстройки «Разработчик»

Еще в «центре обеспечения безопасностью» нажать «Параметры безопасности» (см. рисунок 11).



Рис.11 Настройки безопасности

В параметрах макросов включить все макросы и доверить доступ VBA (см. рисунок 12).

Рис.12 Включение макросов

Также потребуется добавить компонент «Solver» перейдя во вкладку «Разработчик» => «Visual Basic» => «Tools» => «Reference» (см. рисунок 13).



Рис.13 Включение компонента «Solver»

Файл «TZ.xlsm» использует следующий макрос:

Sub makros1()

' makros1 POISK RESH

Range("F28").Select

SolverOk SetCell:="$F$28", MaxMinVal:=2, ValueOf:="0", ByChange:="$E$18:$H$19"

SolverSolve UserFinish:=True

End Sub

Далее запускаем программу «Var16.exe». Появляется окно с заполненными данными согласно варианту: поставщики (Элеватор 1, Элеватор 2) их запасы, потребители (Хлебозавод 1, Хлебозавод 2, Хлебозавод 3) их потребности и затраты на 1 единицу (см. рисунок 14).



Рис.14 Заполнение данных

При нажатии на кнопку «Считать» программа произведет расчеты и будет выведен результат в строку «Оптимальный грузооборот» и «Минимальные затраты». Так же рассчитается оптимальный план перевозок (см. рисунок 15).



Рис.15 Расчет результатов

В программе предусмотрена возможность ввода других данных: расстояний, потребностей, запасов и затрат на 1 единицу. Для верного вычисления результатов должно соблюдаться условие - сумма всех запасов должна быть больше, чем сумма всех потребностей. Если условие не выполнится, то при нажатии на кнопку «Считать» появиться ошибка (см. рисунок 16).



Рис.16 Ошибка

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

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

Q = 148000 тон/км.

А минимальные денежные затраты составят:

S = 3700000 д.е.

Структура программы Delphi

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

Button- простая командная кнопка, используется для реализации в программе команд с помощью обработчика события OnClick этого компонента.

Label предназначен для отображения статического текста, то есть надписей и меток на Форме.

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

Memo - простой текстовый редактор. Memo позволяет вводить многострочный текст с клавиатуры, загружать его из файла, редактировать и сохранять в файл текстового формата.

Переменные в модуле были задействованы

Form1: TForm1;

ap: variant. Переменная Ap - ссылка объекта, возвращенная функцией 'Excel.Application'

Функция возвращает ссылку на объект, представляющий собой переменную типа variant

Тип Variant обеспечивает гибкий универсальный тип данных

procedure TForm1.FormCreate(Sender: TObject);

filename:string - переменная filename связывает путь и имя файла

Эта процедура выполняется сразу же после открытия формы и идет заполнение данных согласно варианту.

Memo1.Text:='';

Memo1.Lines.Add ('Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000,2000,1600 т каждому. Расстояние от элеватора до хлебозаводов указано в таблице. Затраты на 1т/км - 25 д.е');

Edit9.Text:='4200';

Edit10.Text:='1200';

Запись запасов

Edit14.Text:='1000'

Edit15.Text:='2000';

Edit16.Text:='1600';

запись потребностей

Edit17.Text:='25';

запись затрат на еденицу

Edit1.Text:='20';

Edit2.Text:='30';

Edit3.Text:='50';

Edit5.Text:='60';

Edit6.Text:='20';

Edit7.Text:='40';

Присвоение плану перевозок и ячеек с ответами значение «0»

Edit4.Text:='0';

Edit8.Text:='0';

Edit13.Text:='0';

Создается единичный OLE объект. И программа открывает Excel файл, который производит все вычисления

Ap := CreateOleObject('Excel.Application'); Функция возвращает ссылку на объект, представляющий собой переменную типа variant. Результатом выполнения данной процедуры будет запуск приложения Excel на выполнение.

filename:=ExtractFilePath(Application.ExeName)+'\TZ.xlsm';

ExtractFilePath - Извлекает из полного имени файла исполняемый файл.

Ap.Workbooks.Open(filename);

procedure TForm1.Button1Click(Sender: TObject);

переменные zap,pot: real - для записывания результата суммы запасов, и суммы потребностей.

Процедура нажатия на кнопку считать. Сразу после нажатия выполняется условие проверки на баланс. Если сумма запасов больше или равна сумме потребностей, то программа продолжит выполнение дальше. А если сумма запасов меньше сумме потребностей программа выдаст ошибку.

Условие выполнения задачи

zap:=strtofloat(edit9.Text)+strtofloat(edit10.Text);

pot:=strtofloat(edit14.Text)+strtofloat(edit15.Text)+strtofloat(edit16.Text);

if (zap>=pot) then - условный оператор выполняющий условие

else

Вывод ошибки

MessageBox(0,'Задача не может быть решена','Ошибка', MB_OK);

После проверки на баланс и при выполнении условия происходит записывание данных из программы в Exel файл

Ap.Range['E7']:=strtofloat(Edit1.Text);

Ap.Range - для задания объекта, ассоциированного с областью ячеек.

Ap.run('makros1')- Непосредственное выполнение макроса.

После вычислений происходит считывание данных из Exel файла и запись готовых ответов в программу.

Edit1.Text:=Ap.Range['E7'];

Edit2.Text:=Ap.Range['F7'];

Edit3.Text:=Ap.Range['G7'];

procedure TForm1.Button2Click(Sender: TObject);

Кнопка закрытия программы.

Ap.DisplayAlerts := False - отмена запроса о сохранении Exel файла

Ap.Workbooks.close - Закрытие рабочей книги

Ap.Application.Quit - Закрытие Exel файла

Application.Terminate - Закрытие программы

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

В этой процедуре при нажатии на крестик происходит закрытие программы и Exel файла.

Ap.DisplayAlerts := False - отмена запроса о сохранении Exel файла

Ap.Workbooks.close - Закрытие рабочей книги

Ap.Application.Quit - Закрытие Exel файла

Application.Terminate - Закрытие программы

Выводы

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

Была составлена программа, которая разработана в программе Delphi .

В программе удобный и понятный пользовательский интерфейс. Для ввода данных используется клавиатура. Данные, выводимые программой, соответствуют тем, что получены при расчетах вручную - методом наименьшего элемента и методом потенциалов, соответствуют решению в программе TORA и в программе. MicrosoftExcel 2007 реализованную через «Поиск решения»

Для всех способов минимальные денежные затраты равны 3700000 д.е.

Таким образом, поставленная задача была выполнена.

Список используемой литературы

1. Данилин Г.А. Математическое программирование с EXCEL: Учебное пособие для студентов всех специальностей МГУЛа / Г.А. Данилин, В.М. Курзина, П.А. Курзин и др. - М.: МГУЛ. 2005.

2. Корняков В.Н. Программирование документов и приложений MS Office в Delphi. -- СПб.: БХВ-Петербург, 2005. - 496 с : ил.

3. Таха, Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. -- М.: Издательский дом "Вильяме", 2005. -- 912 с: ил.

Размещено на Allbest.ru