Решение открытой транспортной задачи
Общая математическая формулировка открытой транспортной задачи, её опорное решение. Вербальная постановка транспортной задачи и её решение распределительным методом. Интерпретация результатов проученных расчетов и выработка управленческого мероприятия.
Рубрика | Экономико-математическое моделирование |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 16.01.2013 |
Размер файла | 2,2 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
КУРСОВАЯ РАБОТА
на тему: «Решение открытой транспортной задачи»
Содержание
Введение
Глава 1. Теоретические основы транспортной задачи:
1.1 Общая математическая формулировка открытой транспортной задачи
1.2 Методы решения транспортной задачи
1.2.1 Опорное решение транспортной задачи
1.2.2 Метод потенциалов
Глава 2. Построение и решение транспортной задачи:
2.1 Вербальная постановка транспортной задачи
2.2 Решение поставленной задачи распределительным методом «вручную»
2.3 Решение поставленной задачи с помощью средств EXCEL
2.4 Интерпретация результатов расчетов и выработка управленческого решения
Заключение
Список использованной литературы
Введение
Математика необходима в повседневной жизни, следовательно, определенные математические навыки нужны каждому человеку. Нам приходится в жизни считать, мы постоянно используем знания о величинах, характеризующих протяженности, площади, объемы, промежутки времени, скорости и многое другое. Все это пришло к нам на уроках арифметики и геометрии и пригодилось для ориентации в окружающем мире.
Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой и экономикой. Математика является языком естествознания и техники и потому профессия естествоиспытателя и инженера требует серьезного овладения многими профессиональными сведениями, основанными на математике.
Один из классов математических моделей - задачи линейного программирования. Одной из задач линейного программирования является транспортная задача- задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж.
Тема моей курсовой работы «Решение открытой транспортной задачи». Сегодня несомненна необходимость применения математических знаний и математического мышления врачу, лингвисту, историку, и людям других специальностей. Но особенно знание математики необходимы людям точных профессий - финансистам, экономистам. Таким образом, тема моей курсовой работы является актуальной на сегодняшний день.
Объектом курсовой работы является планирование транспортных перевозок, а предметом является использование методов линейного программирования для решения транспортной задачи.
Цель данной работы - закрепление и углубление знаний, полученных за период обучения в решении открытой транспортной задачи. Для достижения этой цели будут выполнены следующие задачи:
1) экономико-математическое моделирование транспортной задачи;
2) выбор одного из методов решения задачи вручную;
3) решение поставленной задачи с помощью средств Excel;
4) интерпретация результатов и выработка управленческого решения.
вербальная постановка расчет транспортная задача
Глава 1. Теоретические основы транспортной задачи
1.1 Общая математическая формулировка транспортной задачи
Задача о размещении (транспортная задача) - это задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи (ТЗ) является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям.
Стандартная транспортная задача определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции.
Транспортная задача делится на два вида:
- транспортная задача по критерию стоимости - определение плана перевозок, при котором стоимость груза была бы минимальна;
- транспортная задача по критерию времени - более важным является выигрыш по времени.
Транспортная задача по критерию стоимости является частным случаем задачи линейного программирования и может быть решена симплексным методом. Однако в силу особенностей задачи, она решается проще.
Особенности экономико-математической модели транспортной задачи:
- система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);
- коэффициенты при переменных системы ограничений равны единице или нулю;
- каждая переменная входит в систему ограничений два раза.
Транспортная задача, в которой суммарные запасы и потребности совпадают, т. е. выполняется условие , называется закрытой моделью; в противном случае - открытой. Для открытой модели может быть два случая:
a) суммарные запасы превышают суммарные потребности ;
b) суммарные потребности превышают суммарные запасы
Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.
Найти минимальное значение линейной функции при ограничениях:
, i = 1, 2, ..., m - (случай а)
, j = 1, 2, ..., n;
, i = 1, 2, ..., m - (случай b)
, j = 1, 2, ..., n,
xij ? 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого:
bn+1 =
В случае (b), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого:
am+1 =
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится. После преобразований задача принимает вид закрытой модели и решается обычным способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика. Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения. Однородный груз сосредоточен у т поставщиков в объемах. Данный груз необходимо доставить n потребителям в объемах. Известны (i=1,2,…,m; j=1,2,…,n)- стоимости перевозки единицы груза от каждого i-ого поставщика каждому j-ому потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи записываются следующим образом в приведенной нище таблице:
Таблица 1. Исходные данные транспортной задачи
B1 |
B2 |
… |
Bn |
||
А1 |
c11 |
c12 |
… |
c1n |
|
А2 |
c21 |
c22 |
… |
c2n |
|
… |
… |
… |
… |
… |
|
Аn |
cm1 |
cm2 |
… |
cmn |
Переменными (неизвестными) транспортной задачи являются (i=1,…,m; i=1,2,…,n)- объемы перевозок от каждого i-ого поставщика каждому j-ому потребителю. Эти переменные могут быть записаны в матрице перевозок
Математическая модель транспортной задачи в общем случае имеет вид:
i=1,2,…,m, (1.1)
j=1,2,…,n, (1.2)
i=1,2,…,m; j=1,2,…,n. (1.3)
Целевая функция задачи выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из m уравнений (1.1) описывает тот факт, что запасы всех m поставщиков вывозятся полностью. Вторая группа из n уравнений (1.2) выражает требования полностью удовлетворить запросы всех n потребителей. Неравенства (1.3) являются условиями не отрицательности всех переменных задачи.
Таким образом, математическая формулировка транспортной задачи состоит в следующем: найти переменные задачи i=1,2,…,m; j=1,2,…,n, удовлетворяющее системе ограничений (1.1), (1.2), условиям не отрицательности (1.3) и обеспечивающее минимум целевой функции.
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. такая задача называется задачей с правильным балансом, а ее модель - закрытой. Если же это неравенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель - открытой.
Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть с правильным балансом.
1.2 Методы решения транспортной задачи
1.2.1 Опорное решение транспортной задачи
Существуют различные методы решения транспортной задачи. Рассмотрим более конкретно некоторые из них.
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Ввиду того, что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.
Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.
1. Метод вычеркивания
Для проверки возможности образования цикла используется так называемый метод вычеркивания, который состоит в следующем.
Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
2. Метод минимальной стоимости
Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимостей транспортной задачи , i=1,2,…,m; j=1,2…,n. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости, и исключается из рассмотрения только одна строка(поставщик) или один столбец (потребитель). Очередную клетку, соответствующую, заполняют также. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и только потом поставщик исключается из рассмотрения. Аналогично поступают с потребителем.
Пример:
Используя метод минимальной стоимости, построить начальное опорное решение транспортной задачи, доставки лекарств из трех складов в четыре аптеки (данные представлены в табл.2):
Таблица 2. Данные задачи
80 |
120 |
160 |
120 |
||
120 |
1 |
3 |
4 |
2 |
|
160 |
4 |
5 |
8 |
3 |
|
200 |
2 |
3 |
6 |
7 |
Решение: запишем отдельно матрицу стоимостей для того, чтобы удобнее было выбирать стоимости, вычеркивать строки и столбцы: (1 4 6 3) среди элементов матрицы стоимостей выбираем наименьшую стоимость. Это стоимость перевозки груза от первого поставщика первому потребителю. В соответствующую клетку (1,1) записываем максимально возможную перевозку (табл. 4). Запасы первого поставщика уменьшаем на 80, Исключаем из рассмотрения первого потребителя, так как его запросы удовлетворены. В матрице С вычеркиваем первый столбец (см. табл.3).
Таблица 3. Матрица стоимостей
80 |
120 |
160 |
120 |
||
120 |
1 80 |
3 |
4 |
2 40 |
|
160 |
4 |
5 |
8 80 |
3 80 |
|
200 |
2 |
3 120 |
6 80 |
7 |
В оставшейся матрицы С наименьшей является стоимость, максимально возможная перевозка, которую можно осуществить от первого поставщика к четвертому потребителю. В соответствующую клетку таблицы записываем перевозку. Запасы первого поставщика исчерпаны, исключаем его из рассмотрения. В матрице С вычеркиваем первую строку. Запросы четвертого потребителя уменьшаем на 40. В оставшейся части матрицы С будет минимальная стоимость. Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку (2,4) запишем, что запросы четвертого потребителя удовлетворены полностью, исключаем его из рассмотрения, вычеркиваем четвертый столбец в матрице С. Уменьшаем запасы второго поставщика. В оставшейся части матрицы С будет минимальная стоимость. Запишем в клетку таблицы (3,2) перевозку. Исключаем из рассмотрения второго потребителя, а из матрицы С второй столбец. Вычисляем. В оставшейся части матрицы С будет наименьшая стоимость. Запишем в клетку таблицы (3,3) перевозку. Исключаем из рассмотрения третьего поставщика, а из матрицы С третью строку. Определяем. В матрице С остался единственный элемент. Записываем в клетку таблицы (2,3) перевозку.
Проверяем правильность построения опорного решения. Число занятых клеток таблицы равно N=m+n-1=3+4-1=6. Применяя метод вычеркивания, проверяем линейную независимость векторов условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице Х: (1 2 5 6)
Решение является «вычеркиваемым» и, следовательно, опорным. Переход от опорного решения к другому в транспортной задаче осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок (осуществляется сдвиг по циклу). Перевозка «загружается» в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение.
Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением. Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Такой цикл называется означенным (см. рис. 1).
Рис. 1. Означенный цикл
Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», и уменьшение объемов перевозок на ту же величину во всех не четных клетках, отмеченных знаком «-».
3. Метод северо - западного угла
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используется запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. При этом нулевые перевозки принято заносить в таблицу только в том случае, когда они попадают в клетку (i,j), подлежащую заполнению, т.е. в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.
Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы условий, соответствующие этим клеткам, линейно независимы.
Необходимо иметь в виду, что метод северо-западного угла не учитывает стоимость перевозок, поэтому, опорное решение, построенное по данному методу, может быть далеким от оптимального.
1.2.2 Метод потенциалов
Широко распространенным методом решения транспортных задач является метод потенциалов. Если допустимое решение (i=1,2,…,m; j=1,2,…n ) транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1,2,…,m )и потребителей (j=1,2,…,n). Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.
Алгоритм решения транспортных задач методом потенциалов:
а) проверить выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводится фиктивный поставщик или потребитель с недостающими запасами или запросами и нулевыми стоимостями перевозок.
b) построить начальное опорное решение (методом минимальной стоимости или каким-либо другим методом), проверить правильность его построения по количеству занятых клеток (их должно быть m+n-1) и убедиться в линейной независимости векторов условий (используется метод вычеркивания).
c) построить систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений, которая имеет бесконечное множество решений. Для нахождения частного решения системы одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам.
d) проверить выполнения условия оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам и те из них, которые больше нуля, записываются в левые нижние углы клеток. Если для всех свободных клеток, то вычисляют значение целевой функции и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, опорное решение не является оптимальным.
e) перейти к опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка.
Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком «-», в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным. Далее перейти к пункту 3 данного алгоритма.
Глава 2. Постановка и решение транспортной задачи
2.1 Вербальная постановка транспортной задачи
На складах трех поставщиков А1, А2, А3 хранится 300, 250 и 200 единиц одного и того же груза. Этот груз требуется доставить четырем потребителям B1, В2, B3 и B4, заказы которых составляют 220, 150, 250 и 180 единиц груза соответственно. Стоимости перевозок ij c единицы груза с i-го склада j -му потребителю указаны в правых верхних углах соответствующих клеток транспортной таблицы, приведенной ниже.
Таблица 4. Транспортная таблица
заказы запасы |
В1 220 |
В2 150 |
В3 250 |
В4 180 |
|
А1 300 |
4 |
5 |
3 |
6 |
|
А2 250 |
7 |
2 |
1 |
5 |
|
А3 200 |
6 |
1 |
4 |
2 |
Составить такой план перевозок груза, при котором общая стоимость всех перевозок была бы минимальной.
2.2 Решение поставленной задачи распределительным методом «вручную»
Поскольку суммарный запас груза, а = 300 + 250 + 200 = 750 меньше суммарной потребности b = 220 + 150 + 250 + 180 = 800, то рассматриваемая транспортная задача является открытой. Сведем ее к закрытой, добавив фиктивного поставщика A4 с нулевыми тарифами перевозок и запасом груза a4 = b ? a = 50. Составим первоначальный план перевозок с помощью метода наименьшей стоимости, заполняя клетки в следующем порядке:
(1,1) - (1,2) - (2,2) - (2,3) - (3,3) - (3,4) - (4,4)
Получим следующую таблицу.
Таблица 5. План перевозок
заказы запасы |
В1 220 |
В2 150 |
В3 250 |
В4 180 |
|
А1 300 |
4 220 |
5 80 |
3 |
6 |
|
А2 250 |
7 |
2 70 |
1 180 |
5 |
|
А3 200 |
6 |
1 |
4 70 |
2 130 |
|
А4 50 |
50 |
Перейдем к анализу полученного плана. В этой задаче m + n ?1= 4 + 4 ?1= 7 и число занятых клеток в имеющемся плане также равно 7. Далее ищем базисное решение:
F= 220*4 + 5*80 + 2*70 + 1*180 + 70*4 + 2*130 + 0*50 = 2140
Проверим это решение на оптимальность:
F(1,3)= 3-5+2-1= -1
F(1,4)= 6-5+2-1+4-2= 4
F(2,1)= 7-4+5-2= 6
F(2,4)= 5-1+4-2= 6
F(3,1)= 6-4+1-2+5-4= 2
F(3,2)= 1-2+1-4= -4
Решение не оптимально, т.к. есть отрицательные оценки. Клетка (3,2) имеет минимальную оценку в отрицательных клетках цикла, минимальное количество груза равно 70. Направляем груз в клетку (3,2) и получаем следующую таблицу.
Таблица 6. План перевозок с изменением направления груза в ячейку (3,2)
заказы запасы |
В1 220 |
В2 150 |
В3 250 |
В4 180 |
|
А1 300 |
4 220 |
5 80 |
3 |
6 |
|
А2 250 |
7 |
2 0 |
1 250 |
5 |
|
А3 200 |
6 |
1 70 |
4 |
2 130 |
|
А4 50 |
50 |
Найдем базисное решение:
F2= -4*70= -280
F= 2140-280= 1860
Проверим найденное решение на оптимальность:
F(1,3)= 3-5+2-1= -1
F(1,4)= 6-5+1-2= 0
F(2,1)= 7-4+5-2= 6
F(2,4)= 5-1+4-2= 6
F(3,1)= 6-4+5-1= 6
F(3,3)= 4-1+2-1= 4
Решение не оптимально, т.к. есть отрицательные оценки. Клетка (1,3) имеет минимальную оценку в отрицательных клетках цикла, минимальное количество груза равно 80. Направляем груз в клетку (1,3) и получаем следующую таблицу.
Таблица 7. План перевозок с изменением направления груза в ячейку (1,3)
заказы запасы |
В1 220 |
В2 150 |
В3 250 |
В4 180 |
|
А1 300 |
4 220 |
5 |
3 80 |
6 |
|
А2 250 |
7 |
2 80 |
1 170 |
5 |
|
А3 200 |
6 |
1 70 |
4 |
2 130 |
|
А4 50 |
50 |
Найдем базисное решение:
F3= -1*80= -80
F= 1860-80= 1780
Проверим данное решение на оптимальность:
F(1,2)= 5-3+1-2= 1
F(1,4)= 6-3+1-2+1-2= 3
F(2,1)= 7-4+3-1+2= 7
F(2,4)= 5-2+1-2+1= 3
F(3,1)= 6-1+2-1+3-4= 5
F(3,4)= 4-1+2-1= 4
Данное решение является оптимальным. Таким образом, фиктивный груз А4= 50 в табл.10 означает, что потребителю B4 будет недопоставлено 50 единиц груза.
2.3 Решение данной задачи с помощью средств EXCEL
На практике подобные задачи решаются, конечно же, при помощи различного программного обеспечения, что позволяет значительно упростить работу и сэкономить время.
Рассмотрим, как это можно сделать в среде электронных таблиц Microsoft Excel. В табличном процессоре Microsoft Excel для решения подобных задач предусмотрена надстройка «Поиск решения». Выполняется следующая подготовительная работа для решения транспортной задачи с помощью средства «Поиск решения» в табличном процессоре Microsoft Excel:
1) вводятся в ячейки диапазона A7:D10 значения спроса
2) вводится в диапазон ячеек A12:D12 матрица расходов.
3) вводятся в ячейки диапазона F7:F10 запасы.
4) в ячейку А15 выводиться оптимальное решение
Для нахождения оптимального решения используем формулу: =СУММПРОИЗВ(A1:D4;A7:D10). Сделать это можно при помощи мастера функций выбрав в разделе «Математические» функцию СУММПРОИЗВ и указав необходимый диапазон (см. рис. 2).
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Рис. 2. Исходные данные листа Microsoft Excel
Далее выбираем команду сервис, Поиск решений и заполняем открывшееся диалоговое окно «Поиск решений». Устанавливаем целевую ячейку, задачу решаем на минимум, изменяем ячейки $A$7:$D$10 и устанавливаем ограничения:
1) $A$12:$D$12 <= $A$14:$D$14
2) $F$7:$F$10 = $H$7:$H$10
3) $A$7:$D$10 >= 0 (см. рис. 3).
Рис. 3. Диалоговое окно Поиск решения
В диалоговом окне «Параметры поиска решения» установить флажок «Линейная модель». После нажатия кнопки «Выполнить» средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (см. рис. 4).
Рис. 4. Полученное решение
Решение найдено. F=1780 (см. рис. 4). Таким образом, получаем, потребителю В4 будет недоставать 50 единиц груза.
2.4 Интерпретация результатов расчетов и выработка управленческого решения
Таким образом, мы получили оптимальное решение. От поставщика А1 будем доставлять потребителю В1 220 единиц груза, а потребителю В3 80 единиц груза. От поставщика А2 будем направлять потребителю В2 80 единиц груза, а потребителю В3 170 единиц груза. От поставщика А3 будем направлять потребителю В2 70 единиц груза и фиктивному потребителю 130 единиц груза. И получаем, что фиктивный груз А4=50 - это означает, что фиктивному потребителю В4 будет недопоставлено 50 единиц груза. Общие затраты на доставку всей продукции, для оптимального решения, составляют 1780 денежных единиц.
В работе представлены отчеты о результатах, об устойчивости и о пределах.
Отчет по результатам включает исходные и конечные значения целевой функции и изменяемых ячеек, а также формул ограничений и дополнительных сведений о наложенных ограничениях (см.рис.5 и рис.6).
Рис.5. Отчет о результатах
Рис.6. Отчет о результатах
Отчет по устойчивости содержит сведения о чувствительности решения (нормируемая стоимость и теневая цена) к изменениям значений влияющих ячеек и ячеек, содержащих формулы ограничений, а также предельные изменения целевых коэффициентов и правых частей ограничений, определяющих границы устойчивости найденных решений (см.рис.7).
Рис.7. Отчет об устойчивости
Отчет по пределам содержит конечные значения целевой и изменяемых ячеек, а также верхних и нижних границ. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время, как влияние остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Верхним пределом - наибольшее значение влияющей ячейки при фиксировании остальных (см.рис.8).
Рис.8. Отчет о пределах
Заключение
Мною была рассмотрена курсовая работа на тему: «Решение открытой транспортной задачи». По окончанию данной работы я могу сказать, что она была для меня как интересной, так и полезной. Благодаря ей я лучше научился разбираться в транспортных задачах. Сама задача мне не показалась достаточно сложной, поэтому при ее выполнении особых проблем не возникало. Также в данном курсе нас познакомили с такой средой как Microsoft Excel. Одной из главных задач данной работы было решение и сравнение транспортной задачи вручную и в среде Microsoft Excel. Подводя итоги данной работы, я убедился, что задача была решена, верно, так как решение совпадает. Но стоит сказать, что решение данной задачи вручную мне понравилось гораздо больше, так как здесь пришлось анализировать различные факторы при нахождении минимального пути. Я надеюсь, что данная работа помогла мне лучше разобраться в данной теме.
Список используемой литературы
1. В.В. Федосеев, А. Н. Гармаш. Экономико-математические методы и прикладные модели: учебное пособие для вузов. - М.: Финстатинформ, 1997.
2. Абчук В.А., Экономико-математические методы: учебное пособие для вузов. - СПб.: Союз,1999.
3. Советов Б.Я, Яковлев С.А., Моделирование систем: практикум. - М.: Высшая школа,1999.
4. Замков О.О., Толстопятенко А.В., Черемных Ю.Н., Математические методы в экономике: учебное пособие для вузов. - М.: ДИС, 1997.
Размещено на Allbest.ru
...Подобные документы
Применение линейного программирования для решения транспортной задачи. Свойство системы ограничений, опорное решение задачи. Методы построения начального опорного решения. Распределительный метод, алгоритм решения транспортной задачи методом потенциалов.
реферат [4,1 M], добавлен 09.03.2011Математическая постановка и алгоритм решения транспортной задачи. Сбалансированность и опорное решение задачи. Методы потенциалов и северо-западного угла. Блок-схема. Формы входной и выходной информации. Инструкция для пользователя и программиста.
курсовая работа [113,8 K], добавлен 10.11.2008Математическая формулировка экономико-математической задачи. Вербальная постановка и разработка задачи о составлении графика персонала. Решение задачи о составлении графика персонала с помощью программы Microsoft Excel. Выработка управленческого решения.
курсовая работа [1,2 M], добавлен 12.01.2018Формулировка проблемы в практической области. Построение моделей и особенности экономико-математической модели транспортной задачи. Задачи линейного программирования. Анализ постановки задач и обоснования метода решения. Реализация алгоритма программы.
курсовая работа [56,9 K], добавлен 04.05.2011Составление системы ограничений и целевой функции по заданным параметрам. Построение геометрической интерпретации задачи, ее графическое представление. Решение транспортной задачи распределительным методом и методом потенциалов, сравнение результатов.
контрольная работа [115,4 K], добавлен 15.11.2010Основные методы решения задачи оптимального закрепления операций за станками. Разработка экономико-математической модели задачи. Интерпретация результатов и выработка управленческого решения. Решение задачи "вручную", используя транспортную модель.
курсовая работа [1,0 M], добавлен 25.01.2013Математическая постановка задачи и выбор алгоритма решения транспортной задачи. Проверка задачи на сбалансированность, её опорное решение и метод северо-западного угла. Транспортная задача по критерию времени, поиск и улучшение решения разгрузки.
курсовая работа [64,7 K], добавлен 14.10.2011Решение графическим методом задачи линейного программирования с двумя неизвестными. Решение транспортной задачи методом северо-западного угла и методом минимальной стоимости. Системы массового обслуживания. Стохастическая модель управления запасами.
контрольная работа [458,1 K], добавлен 16.03.2012Сущность многопериодической транспортной задачи, построение дерева проблем. Особенности морфологического, функционального и информационного описания логистической системы. Формулировка транспортной задачи, представление ее математической модели.
курсовая работа [314,2 K], добавлен 12.05.2011Основные подходы и способы решения транспортной задачи, ее постановка и методы нахождения первоначального опорного решения. Математическая модель транспортной задачи и алгоритм ее решения методом потенциалов. Составление опорного плана перевозок.
курсовая работа [251,0 K], добавлен 03.07.2012Понятие и содержание транспортной задачи, структура ее ограничений, составление соответствующей матрицы. Существующие методы ее разрешения, история их разработки и анализ эффективности: венгерский, потенциалов. Определение потенциалов текущего плана.
контрольная работа [72,7 K], добавлен 23.04.2016Содержание методов аппроксимации Фогеля, потенциала, наименьшей стоимости и северо-западного угла как путей составления опорного плана транспортной задачи на распределение ресурсов с минимальными затратами. Ее решение при помощи электронных таблиц.
курсовая работа [525,7 K], добавлен 23.11.2010Характеристика табличного и канонического представления линейно-программной модели планирования. Содержательная интерпретация симплекс-метода. Корректировка оптимального плана по нерентабельной продукции. Постановка и решение транспортной задачи.
курс лекций [10,1 M], добавлен 11.07.2010Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Экономико-математическая модель прикрепления пунктов отправления к пунктам назначения, расчет оптимального плана перевозок. Решение транспортной задачи метолом потенциалов (перераспределение ресурсов по контуру), пример вычислительного алгоритма.
учебное пособие [316,8 K], добавлен 17.10.2010Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.
учебное пособие [126,0 K], добавлен 07.10.2014Транспортная задача (Т-задача) как одна из наиболее распространенных специальных задач линейного программирования. Порядок и закономерности постановки данной задачи, аналитический и графический методы. Открытые и закрытые транспортные модели, их решение.
контрольная работа [419,4 K], добавлен 06.08.2010Пример решения графическим методом задачи линейного программирования с двумя неизвестными. Решение транспортной задачи методами северо-западного угла и минимальной стоимости. Стохастическая модель управления запасами, ее значение для предприятий.
контрольная работа [606,2 K], добавлен 04.08.2013- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Методы линейного программирования; теория транспортной задачи, ее сущность и решение на примере ООО "Дубровчанка+": характеристика предприятия, организационная структура и статистические данные. Построение и решение экономико-математической модели.
курсовая работа [652,5 K], добавлен 04.02.2011