Xreferat.com » Рефераты по информатике и программированию » Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН

КАЗАХСКИЙ ГОСУДАРСТВЕННЫЙ ЖЕНСКИЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ

КАФЕДРА ИНФОРМАТИКИ


Дипломная работа

ПО ТЕМЕ:

«Решение транспортной задачи линейного программирования в среде MS Excel»


Выполнила: студентка 4курса,

протокол № о/о, р/о, спец. «Информатика»

Оспанова А.А.

Научный руководитель:

к.т.н., доцент старший преподаватель

Г.И. Салгараева Мусиралиев Ж.А.


Алматы 2008 г.

СОДЕРЖАНИЕ


ВВЕДЕНИЕ

Глава I Задачи линейного программирования

1.1 Общая характеристика задачи линейного программирования

1.2 Математическая постановка задачи линейного программирования

Глава II Основные методы решения транспортной задачи линейного программирования

2.1 Математическая постановка транспортной задачи

2.2 Решение транспортной задачи с помощью программы Ms Excel

2.3 Рекомендации по решению задач оптимизации с помощью надстройки «Поиск решения»

Глава III Двойственная задача линейного программирования

3.1 Математическая формулировка двойственной задачи линейного программирования

3.2 Математическая постановка двойственной задачи о красках

3.3 Решение двойственной задачи о красках с помощью программы Ms Excel

Заключение

Литература


Введение


Транспортная задача.

В некотором географическом регионе имеется фиксированное число пунктов производства и хранения некоторого однородного продукта и конечное число пунктов потребления этого продукта . В качестве продукта может выступать, например, нефть, уголь, песок, цемент, т.д. Для каждого из пунктов производства и хранения известен объем производства продукта или его запаса. Для каждого пункта потребления задана потребность в продукте в этом пункте потребления.

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


Решение транспортной задачи линейного программирования в среде MS Excel

Рисунок1. Иллюстрация транспортной задачи для двух пунктов производства и трех пунктов потребления

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

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

Транспортная задача: Уменьшение затрат на перевозку.

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

Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводятся именно к этой задаче.

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А1,А2,…,Ат в п пунктов назначения В1,В2,..,Вп. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза. Обозначим через сij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через ai-запасы груза в j-м пункте отправления, через bj-потребности в грузе в j-м пункте назначения , а через xij-количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции:

Решение транспортной задачи линейного программирования в среде MS Excel, [1]


при условиях:

Решение транспортной задачи линейного программирования в среде MS ExcelРешение транспортной задачи линейного программирования в среде MS Excel [2]


Решение транспортной задачи линейного программирования в среде MS Excel [3]


Решение транспортной задачи линейного программирования в среде MS Excel [4]


Поскольку переменныеРешение транспортной задачи линейного программирования в среде MS Excelудовлетворяют системам уравнений(2) и (3) и условию неотрицательности (4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения (условие (2)), вывоз имеющегося груза из всех пунктов отправления (условие (3)), а также исключаются обратные перевозки (условие (4)).

Определение 1. Всякое неотрицательное решение системы линейных уравнений (2) и (3), определяемое матрицей Х=(Решение транспортной задачи линейного программирования в среде MS Excel) (i=1,…m;j=1,…n), называется планом транспортной задачи.

Определение2. План Решение транспортной задачи линейного программирования в среде MS ExcelРешение транспортной задачи линейного программирования в среде MS Excel=(Решение транспортной задачи линейного программирования в среде MS Excel) (i=1,…m;j=1,…n), при котором функция (1) принимает своё минимальное значение, называется оптимальным планом транспортной задачи.

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

Очевидно, общее наличие груза у поставщиков равно:


Решение транспортной задачи линейного программирования в среде MS Excel,

а общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.


Решение транспортной задачи линейного программирования в среде MS Excel


единиц.

Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel=Решение транспортной задачи линейного программирования в среде MS Excel, [5]


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


Таблица 1

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

Пункты

отправления

Пункты назначения Запасы

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel



Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel


Решение транспортной задачи линейного программирования в среде MS Excel

Потреб

ности

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel

Решение транспортной задачи линейного программирования в среде MS Excel



В случае превышения запаса над потребностью


Решение транспортной задачи линейного программирования в среде MS Excel>Решение транспортной задачи линейного программирования в среде MS Excel,


вводится фиктивный (n+1)-й пункт назначения с потребностью


Решение транспортной задачи линейного программирования в среде MS Excel=Решение транспортной задачи линейного программирования в среде MS Excel-Решение транспортной задачи линейного программирования в среде MS Excel


и соответствующие тарифы считаются равными нулю: Решение транспортной задачи линейного программирования в среде MS Excel=0 (i=1,…m). Полученная таким образом задача является транспортной задачей, для которой выполняется равенство (5).

Аналогично, при


Решение транспортной задачи линейного программирования в среде MS Excel<Решение транспортной задачи линейного программирования в среде MS Excel,


вводится фиктивный (m+1)-й пункт отправления с запасом груза


Решение транспортной задачи линейного программирования в среде MS Excel=Решение транспортной задачи линейного программирования в среде MS Excel-Решение транспортной задачи линейного программирования в среде MS Excel

и тарифы пологаются равными нулю: Решение транспортной задачи линейного программирования в среде MS Excel=0 (j=1,…m). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Число переменных Решение транспортной задачи линейного программирования в среде MS Excel в транспортной задаче с m пунктами отправления и пунктами назначения равно m n, а число уравнений в системах (2) и (3) равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше-то вырожденным.

Для определения опорного плана существует несколько методов. (Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом). Для определения оптимального воспользуемся средством Поиска решений, реализованного в Excel.

Допустим, что ваша фирма занимается переработкой некоторого сырья на нескольких заводах (потребители-З1,З2,…), расположенных в разных районах города. Сырье поставляется со складов (поставщики-П1,П2,…), расположенных в нескольких городах области. Стоимость сырья одинаковая, однако, перевозка со склада и завода. Потребность заводов в сырье различна, и запасы на каждом складе ограничены. Требуется определить: с какого склада, на какой завод поставлять, сколько сырья для минимизации общих затрат на перевозку.

В нашем примере обозначим заводы З1,З2,З3,З4, а склады П1,П2,П3,П4,П5. Стоимость перевозки измеряется в тенге на тонну груза, а потребность заводов и складские запасы - в тоннах.


ГЛАВА I Задачи линейного программирования


К классу линейного программирования относятся такие задачи однокритериальной оптимизации, в которых переменные являются непрерывными и неотрицательными, целевая функция является линейной функцией своих аргументов, а ограничения могут быть представлены в форме линейных неравенств и равенств. При этом на значения переменных не накладываются никакие дополнительные ограничения, такие как, например, ограничения целочисленности или булевости.

На формирование линейного программирования в качестве самостоятельного направления научно-прикладных исследований наибольшее влияние оказали американские ученые Дж. Данциг, Т. Купмас, Дж. фон Нейман и ученые из России Л.В. Канторович, А.С. Немировский, Л.Г. Хачиян и Д.Б. Юдин. Хотя необходимость создания специальных методов решения неклассических оптимизационных задач осознавалась и раньше, в частности, экономистами и военными специалистами во времена второй мировой войны, только в послевоенное время были разработаны теоретические основы линейного программирования и предложены специальные методы решения соответствующих практических задач.

Собственно термин «линейное программирование» впервые появился в 1951 году в работах Дж. Дангинца и лауреата Нобелевской премии по экономике Т. Купманса. Однако общепризнанно, что первые исследования по линейному программированию, связанные с формулировкой основной задачи, рассмотрением приложений, нахождением критерия оптимальности, экономической интерпретацией, были выполнены в конце 30-х годов ХХ в. в СССР лауреатом Нобелевской премии по экономике Л.В. Канторовичем. По поводу Дж. Данциг в одной из своих монографий отмечает, что «Конторовича Л.В. следует признать первым, кто обнаружил, что широкий класс важнейших производственных задач поддается четкой математической формулировке, которая, по убеждению, дает возможность подходить к задачам с количественной стороны и решать их численными методами…»

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


1.1 Общая характеристика задачи линейного

программирования


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


1.2 Математическая постановка задачи линейного

программирования


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


f(x1,x2…,,x n)®Решение транспортной задачи линейного программирования в среде MS Excel где (1.1)

Решение транспортной задачи линейного программирования в среде MS ExcelРешение транспортной задачи линейного программирования в среде MS Excel x1,x2…,,x nРешение транспортной задачи линейного программирования в среде MS Excel (1.2)

(kРешение транспортной задачи линейного программирования в среде MS Excel{1,2,…,m}).


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

Целевая функция f(x1,x2…,,x n ) предполагается линейной относительно всех своих переменных, т.е. может быть представлена в форме всех своих представлена в форме: f(x1,x…,,x n)=с1х1+с2х2+…+с n x n.

Левые части ограничений g k(x1,x2…,,x n) (Решение транспортной задачи линейного программирования в среде MS Excel{1,2,…,m}) также является линейными функциями относительно своих переменных x1,x2…,,x n, т.е. могут быть представлены в форме: g k(x1,x2…,,x n)=ак1х+ак2х2+…+а к n x n.

Переменные x1,x2…,,x n могут принимать свои значения только из множество неотрицательных действительных чисел R1+ ,т.е. хi Решение транспортной задачи линейного программирования в среде MS Excel R1+ (Решение транспортной задачи линейного программирования в среде MS Excel{1,2,…,n}).

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

Необходимо найти максимум линейной целевой функции n переменных x1,x2…,,x n Решение транспортной задачи линейного программирования в среде MS Excel R1+ следующего вида:


с1х1+с2х2+…+с n x n ®Решение транспортной задачи линейного программирования в среде MS Excel (1.3)

где множество допустимых альтернатив Решение транспортной задачи линейного программирования в среде MS ExcelРешение транспортной задачи линейного программирования в среде MS Excel формируется следующей системой ограничений типа равенств и неравенств:


аi1х+аi2х2+…+а in x n=bi (Решение транспортной задачи линейного программирования в среде MS Excel{1,2,…,q}). (1.4)


ак1х+ак2х2+…+а к n x n.Решение транспортной задачи линейного программирования в среде MS Excelbk (Решение транспортной задачи линейного программирования в среде MS Excel{q+1,2,…,m}). (1.5)


В математической постановке общей задачи линейного программирования через сi, aki , bk (Решение транспортной задачи линейного программирования в среде MS Excel{1,2,…,n}),(Решение транспортной задачи линейного программирования в среде MS Excel{1,2,…,m}) обозначены постоянные величины, которые могут принимать произвольные, не обязательно целочисленные значения, определяемые спецификой конкретной задачи линейного программирования.

В случае отсутствия ограничений типа равенств (1.4), т.е. при q=0, задача линейного программирования называется стандартной задачей линейного программирования, которая, с учетом сделанных предположений, может быть записана в следующем виде:


с1х1+с2х2+…+с n x n ®Решение транспортной задачи линейного программирования в среде MS Excel (1.6)


где множество допустимых альтернатив Решение транспортной задачи линейного программирования в среде MS Excel формируется следующей системой ограничений типа неравенств:


Решение транспортной задачи линейного программирования в среде MS ExcelРешение транспортной задачи линейного программирования в среде MS Excel (1.7)


и x1,x2…,,x nРешение транспортной задачи линейного программирования в среде MS Excel 0

С другой стороны, при отсутствии ограничений типа неравенств (1.5), т.е. при q=m, задача линейного программирования называется канонической или основной задачей линейного программирования, которая с учетом сделанных предположений, может быть записана в следующем виде:


с1х1+с2х2+…+с n x n ®Решение транспортной задачи линейного программирования в среде MS Excel (1.8)


где множество допустимых альтернатив Решение транспортной задачи линейного программирования в среде MS Excelформируется следующей системой ограничений типа неравенств:


Решение транспортной задачи линейного программирования в среде MS Excel (1.9)


и x1,x2…,,x n

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: