МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
КАЗАХСКИЙ ГОСУДАРСТВЕННЫЙ ЖЕНСКИЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ
КАФЕДРА ИНФОРМАТИКИ
Дипломная работа
ПО ТЕМЕ:
«
Решение транспортной задачи линейного программирования в среде
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
Заключение
Литература
Введение
Транспортная задача.
В некотором географическом регионе имеется фиксированное число пунктов производства и хранения некоторого однородного продукта и конечное число пунктов потребления этого продукта . В качестве продукта может выступать, например, нефть, уголь, песок, цемент, т.д. Для каждого из пунктов производства и хранения известен объем производства продукта или его запаса. Для каждого пункта потребления задана потребность в продукте в этом пункте потребления.
Требуется определить оптимальный план перевозок продукта, так чтобы потребности во всех пунктах потребления были удовлетворены, а суммарные затраты на транспортировку всей продукции были минимальными.
Рисунок1. Иллюстрация транспортной задачи для двух пунктов производства и трех пунктов потребления
Очевидно, оценочной функцией в данной задаче являются суммарные затраты на транспортировку всей продукции, а ограничениями служат объемы производства и потребности в продукте в каждом пункте потребления.
Данная задача также является одной из классических задач линейного программирования, методы ее решения мы будем рассматривать далее. В бизнес приложениях эта задача известна как задача о перемещении товаров со складов на торговые точки или задача о планировании цепочек поставок. В случае штучного товара, например, телевизоры, компьютеры, пылесосы, автомобили и пр., соответствующая транспортная задача относится к классу задач целочисленного программирования.
Транспортная задача: Уменьшение затрат на перевозку.
В этой работе мы рассмотрим решение классической транспортной задачи Excel 7.0 позволяет находить оптимальное решение, сохраняя заданные ограничения.
Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводятся именно к этой задаче.
1.
Математическая постановка транспортной задачи.
Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А1,А2,…,Ат в п пунктов назначения В1,В2,..,Вп. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза. Обозначим через сij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через ai-запасы груза в j-м пункте отправления, через bj-потребности в грузе в j-м пункте назначения , а через xij-количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции:
, [1]
при условиях:
[2]
[3]
[4]
Поскольку переменныеудовлетворяют системам уравнений(2) и (3) и условию неотрицательности (4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения (условие (2)), вывоз имеющегося груза из всех пунктов отправления (условие (3)), а также исключаются обратные перевозки (условие (4)).
Определение 1. Всякое неотрицательное решение системы линейных уравнений (2) и (3), определяемое матрицей Х=() (i=1,…m;j=1,…n), называется планом транспортной задачи.
Определение2. План =() (i=1,…m;j=1,…n), при котором функция (1) принимает своё минимальное значение, называется оптимальным планом транспортной задачи.
Обычно исходные данные транспортной задачи записывают в виде (см. таблицу 1.)
Очевидно, общее наличие груза у поставщиков равно:
,
а общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.
единиц.
Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.
=, [5]
То модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.
Таблица 1
Теорема 1
. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (5)
| Пункты отправления |
Пункты назначения |
Запасы |
||||
|
|
… |
|
… |
|
||
|
|
|
|
|
|
||
| … |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
||
| … |
… |
… |
… |
… |
… |
… |
|
|
|
|
|
|
||
| Потреб ности |
|
… |
|
… |
|
|
В случае превышения запаса над потребностью
>,
вводится фиктивный (n+1)-й пункт назначения с потребностью
=-
и соответствующие тарифы считаются равными нулю: =0 (i=1,…m). Полученная таким образом задача является транспортной задачей, для которой выполняется равенство (5).
Аналогично, при
<,
вводится фиктивный (m+1)-й пункт отправления с запасом груза
=-
и тарифы пологаются равными нулю: =0 (j=1,…m). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.
Число переменных в транспортной задаче с 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)® где (1.1)
x1,x2…,,x n (1.2)
(k{1,2,…,m}).
при этом следует принимать во внимание следующие принципиальные предположения о характере целевой функции и левых частей ограничений:
1. Целевая функция f(x1,x2…,,x n ) предполагается линейной относительно всех своих переменных, т.е. может быть представлена в форме всех своих представлена в форме: f(x1,x…,,x n)=с1х1+с2х2+…+с n x n.
2. Левые части ограничений g k(x1,x2…,,x n) ({1,2,…,m}) также является линейными функциями относительно своих переменных x1,x2…,,x n, т.е. могут быть представлены в форме: g k(x1,x2…,,x n)=ак1х+ак2х2+…+а к n x n.
3. Переменные x1,x2…,,x n могут принимать свои значения только из множество неотрицательных действительных чисел R1+ ,т.е. хi R1+ ({1,2,…,n}).
С учетом сделанных предположений общая задача линейного программирования может быть сформулирована следующим образом.
Необходимо найти максимум линейной целевой функции n переменных x1,x2…,,x n R1+ следующего вида:
с1х1+с2х2+…+с n x n ® (1.3)
где множество допустимых альтернатив формируется следующей системой ограничений типа равенств и неравенств:
аi1х+аi2х2+…+а in x n=bi ({1,2,…,q}). (1.4)
ак1х+ак2х2+…+а к n x n.bk ({q+1,2,…,m}). (1.5)
В математической постановке общей задачи линейного программирования через сi, aki , bk ({1,2,…,n}),({1,2,…,m}) обозначены постоянные величины, которые могут принимать произвольные, не обязательно целочисленные значения, определяемые спецификой конкретной задачи линейного программирования.
В случае отсутствия ограничений типа равенств (1.4), т.е. при q=0, задача линейного программирования называется стандартной задачей линейного программирования, которая, с учетом сделанных предположений, может быть записана в следующем виде:
с1х1+с2х2+…+с n x n ® (1.6)
где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:
(1.7)
и x1,x2…,,x n 0
С другой стороны, при отсутствии ограничений типа неравенств (1.5), т.е. при q=m, задача линейного программирования называется канонической или основной задачей линейного программирования, которая с учетом сделанных предположений, может быть записана в следующем виде:
с1х1+с2х2+…+с n x n ® (1.8)
где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:
(1.9)
и x1,x2…,,x n 0.
При рассмотрении общих особенностей задачи линейного программирования удобной оказывается стандартная форма математической постановки задачи линейного программирования (1.6) и (1.7). Анализ множества допустимых альтернатив стандартной задачи линейного программирования (1.6) и (1.7) позволяет прийти к выводу о справедливости только одной из трех возможных ситуаций:
1. Система ограничений (1.7) противоречива или несовместна, т.е. не существует ни одного выбора значений x1,x2…,,x которые удовлетворяют ограничениям (1.7). В этом случае задача линейного программирования не имеет решения.
2. Система ограничений (1.7) не является противоречивой, однако соответствующая ей область пространства R
n является неограниченной. В этом случае задача линейного программирования не имеет решения, в случае, если линейная функция (1.6) не ограничена в неограниченной области, соответствующей множеству допустимых альтернатив .
3. Система ограничений (1.7) не является противоречивой, и при этом соответствующая ей область пространства R
n является ограниченной. В этом случае задача линейного программирования имеет решения.
В последней ситуации задача линейного программирования может иметь либо единственное решение, либо континуум решений. Континуум решений имеет место в том случае, когда линейная целевая функция оказывается параллельной функции левой части одного из ограничений.
ГЛАВА
II
Основные методы решения задач линейного программирования
В общем случае существует два подхода к решению задач оптимизации. С одной стороны, для решения задачи линейного программирования теоретически может быть использован некоторый аналитический способ решения, применимый для решения задач оптимизации в общей постановке.
Однако использование для решения задач линейного программирования аналитического способа решения, основанного, например, на методе множителей Лагранжа, с учетом дифференцируемости целевой функции и ограничений, связано с преодолением серьезных трудностей вычислительного характера. В этом случае, даже для небольшого числа переменных и ограничений, решения задачи линейного программирования сводится к нахождению частных производных функции Лагранжа с последующим решением системы уравнений с большим числом переменных. Именно по этой причине аналитический способ решения задач линейного программирования не используется на практике.
С другой стороны для решения задачи линейного программирования могут быть использованы алгоритмические методы решения, применимые для решения задач оптимизации в общей постановке. Эти методы основываются на идее градиентного поиска для задач оптимизации с ограничениями.
Однако наибольшее применение для задач линейного программирования получили алгоритмические способы решения соответствующих задач, которые учитывают специфические особенности целевой функции и множества допустимых решений. Из алгоритмических способов следует отметить получивший широкую известность симплекс- метод
для решения задач линейного программирования и метод потенциалов
для решения транспортной задачи.
Для решения задач линейного программирования в программе MS EXCEL реализованы приближенные методы их решения с достаточно высокой степенью точности. Оценить получаемых решений можно посредством сравнения аналитических и алгоритмических решений отдельных практических задач.
2.1 Математическая постановка транспортной задачи
В общем случае математическая постановка транспортной задачи может быть сформулирована в следующем виде. Имеется m пунктов производства или хранения и n пунктов потребления некоторого однородного продукта (например, уголь, песок цемент и т. п.). Для каждого из пунктов задан аi –объем производства или запаса продукта в i-том пункте (i{1,2,…,m}), а для каждого пункта потребления задана bj – потребность в продукте в j-том пункте потребления (j{1,2,…,n}). Известна сij – стоимость перевозки или транспортировки одной единиц продукта из i-го пункта производства в j-й пункт потребления. Требуется определить оптимальный план перевозок продукта, так чтобы потребность во всех пунктах потребления были удовлетворены, а суммарные затраты на транспортировки всей продукции были минимальными.
Ведем в рассмотрение следующие переменные: хij- количество транспортируемого продукта или объем перевозок из i-го пункта производства в j-й пункт потребления. Тогда в общем случае математическая постановка транспортной задачи может быть сформулирована следующим образом.
, (2.1)
где множество допустимых альтернатив формируется следующей системой отграничений типа неравенств:
Следует заметить, что, в отличие от стандартной задачи линейного программирования, в математической постановке транспортной задачи в виде (2.1)-(2.2) для удобства используются переменные с двумя индексами.
При этом общее число переменных транспортной задачи равно: mn, что делает возможным сформулировать эквивалентную математическую постановку транспортной задачи с одноиндексными переменными.
Классическая транспортная задача линейного программирования является сбалансированной или закрытой, т.е. формулируется в форме, когда имеет место равенство общего объема производства рассматриваемого продукта общему объему его потребления. Этому условию соответствует отдельное ограничение (2.5). В противном случае, если равенство (2.5) не имеет места, то транспортная задача называется несбалансированной или открытой.
На практике встречаются различные модификации транспортной задачи. Наиболее известные из них используют дополнительную структуру типа графа для задания структуры транспортной сети, соединяющей пункты производства и потребления. Соответствующая транспортная задача может быть сформулирована в сетевой постановке применительно к конкретному графу и поэтому относится к классу задач оптимизации на графах.
В то же время классическая транспортная задача может быть дополнена условиями на ограничение сверху возможных значений некоторых или всех переменных: где hij-пропускная способность транспорта между i-м пунктом производства и j-м пунктом потребления. Как нетрудно заметить, подобная модификация приведет к включению в модель (2.1)-(2.5) дополнительных ограничений. Однако эти дополнительные ограничения не оказывают существенного влияния на процесс их решения с помощью программы Ms Excel.
2.2 Решения транспортной задачи с помощью программы Ms Excel
Для решения классической транспортной задачи с помощью программы Ms Excel необходимо задать конкретные значения параметрам исходной задачи. Для определения рассмотрим задачу оптимального планирования перевозок бензина некоторой марки между нефтеперерабатывающими заводами (НПЗ) и автозаправочными станциями (АЗС). В этом случае в качестве транспортируемого продукта рассматривается бензин, в качестве пунктов производства- 3 нефтеперерабатывавающих завода (т=3), а в качестве пунктов потребления- 4 автозаправочные станции (п=4).
Объемы производства бензина следующие: НПЗ №1- 10 т, НПЗ №2- 14 т, НПЗ №3- 17 т. Объемы потребления бензина следующие: АЗС №1-15 п, АЗС №2- 12 п, АЗС №3-8,5 т, АЗС №4-5,5 т. Стоимость транспортировки одной тонны бензина между НПЗ и АЗС заданна в форме следующей таблицы:
Таблица 2.1. Стоимость транспортировки бензина
Между НПЗ и АЗС (в тысяч тенге)
| Пункты потребления / Пункты производства |
АЗС №1 |
АЗС №2 |
АЗС №3 |
АЗС №4 |
| НПЗ №1 |
3 |
5 |
7 |
11 |
| НПЗ №2 |
1 |
4 |
6 |
3 |
| НПЗ №3 |
5 |
8 |
12 |
7 |
Соответствующая математическая постановка рассматриваемой индивидуальной транспортной задачи может быть записана в следующем виде:
3х11+5х12+7х13+11х14+х21+4х22+6х23+3х24+ (2.6)
+5х31+8х32+12х33+7х34→
где множество допустимых альтернативформируется следующей системой ограничений типа равенств:
(2.7)
Заметим, что первые 3 ограничения данной задачи соответствуют общему ограничению (2.2), следующие 4 ограничения- общему ограничению (2.3), а последнее ограничение- общему ограничению (2.5).
При этом общее ограничение (2.4), соответствующее требованию сбалансированности транспортной задачи не входит в математическую модель рассматриваемой индивидуальной задачи. Это вполне допустимо, поскольку непосредственная проверка позволяет установить выполнение общего ограничения (2.4), а значит, исходная транспортная задача (2.6) и (2.7) является сбалансированной.
Для решения сформулированной индивидуальной транспортной задачи с помощью программы MS Excel создадим в книге Линейное программирование новый лист и изменим его имя на Транспортная задача. Для решения задачи выполним следующие подготовительные действия:
1.Внесем необходимые надписи в ячейки A5:A10, B1, F1. B5:G5, как это изображено на рисунке 2.1. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решения рассматриваемой транспортной задачи.
2. В ячейки В2:Е4 введем значение коэффициентов целевой функции (таблица 2.1).
3. В ячейки F2, введем формулу: =суммпроизв(В2:Е2; В6:Е8), которая представляет целевую функцию (2.6).
4. В ячейки G6:G8 и B10:E10 введем значения, соответствующие правым частям ограничений (2.7).
5. В ячейку F6 введем формулу: =сумм (В6:Е6), которая представляет первое ограничение (2.7).
6. Скопируем формулу, введенную в ячейку F6, в ячейки F7 и F8.
7. В ячейку В9 введем формулу: =сумм (В6:В8), которая представляет четвертое ограничение (2.7).
8. Скопируем формулу, введенную в ячейку В9, в ячейки C9, D9 и E9.
Внешний вид рабочего листа MS Office Excel с исходными данными для решения транспортной задачи показан на рисунке 2.1.
Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис│Поиск решения…
После появления диалогового окна Поиск решения следует выполнить следующие действия:
1.В поле с именем Установить целевую ячейку: ввести абсолютный
адрес ячейки $F$2.
2.Для группы Равной: выбрать вариант поиска решения- минимальному значению.
Рисунок. 2.1 Исходные данные для решения
транспортной задач
3. В поле с именем Изменяя ячейки: ввести абсолютный адрес диапазона ячеек $B$2:$E$4.
4.Добавить 7 ограничений, соответствующих базовым ограничениям исходной постановки решаемой транспортной задачи. С этой целью выполнить следующие действия:
· для задания первого ограничения в исходном диалоговом окне Поиск решения нажать кнопку с надписью Добавить;
· в появившемся дополнительном окне выбрать ячейку $F$6, которая
должна отобразиться в поле с именем Ссылка на ячейку;
· в качестве знака ограничений из выпадающего списка выбрать строгое неравенство “=”;
· в качестве значения правой части ограничения выбрать ячейку $С$6;
· для добавления первого ограничения в дополнительном окне нажать кнопку с надписью Добавить;
· аналогичным образом задать оставшиеся 6 ограничений.
5.Добавить последнее ограничение на неотрицательность значений переменных задачи. Внешний вид диалогового окна мастера поиска решения с ограничениями для транспортной задачи изображен на рисунке 2.2.
6.В дополнительном окне параметров поиска решения следует выбрать отметки Линейная модель и Неотрицательные значения.
Рисунок 2.2. Параметры мастера поиска решения и базовых
ограничения для транспортной задачи
После задания ограничений и целевой функции можно приступить к поиску численного решения, для чего следует нажать кнопку Выполнить. После выполнения расчетов программой MS Excel будет получено количественное решение, которое имеет следующий вид рисунок 2.3.
Рисунок 2.3 Результат количественного
решения транспортной задачи
Результатом решения транспортной задачи являются найденные оптимальные значения переменных: х11=0, х12=1,5, х13=8,5, х14=0, х21=14, х22=0, х23=0, х24=0, х31=1, х32=10,5, х33=0, х34=5,5, которым соответствует значение целевой функции: f opt = 208,5. При выполнении расчетов для ячеек В6:Е8 был выбран числовой формат с тремя знаками после запятой.
Анализ найденного решения показывает, что для удовлетворения потребностей АЗС №1 следует транспортировать 14т бензина из НПЗ №2 и 1т- из НПЗ №3, для удовлетворения потребностей АЗС №2 следует транспортировать 1,5 т бензина из НПЗ №1 и 10,5т – из НПЗ №3, для удовлетворения потребностей АЗС №3 следует транспортировать 8,5 т бензина из НПЗ №1 и, наконец, для удовлетворения потребностей АЗС №4 следует транспортировать 5,5 т бензина из НПЗ №3. При этом общая стоимость найденного плана перевозок составит 208,5 тысяч тенге.
Рисунок 2.4 Отчет по результатам поиска решения
2.3 Решение транспортной задачи с помощью методов
потенциалов
Для оценки точности и правильности результатов решения транспортных задач линейного программирования, полученных с помощью программных средств, в общем случае можно воспользоваться симплекс-методом. Однако специально для решения транспортной задачи линейного программирования был разработан метод потенциалов. Основная идея этого метода основывается на критерии оптимальности, который может быть сформулирован следующим образом.
Для того чтобы исходная закрытая транспортная задача линейного программирования (2.1) - (2.5) имела оптимальное решение, необходимо и достаточно существование таких неотрицательных чисел {v1,v2,v3,…,vn, u1,u2,…,um}, которые обеспечивают выполнение двух групп условий:
, (2.8)
и если некоторое
>0 то ui+uj=cij. (2.9)
Соответствующие данным условиям числа {v1,v2,…,vn, u1,u2,…,um} получили название потенциалов. Очевидно, данные условия могут служить признаком окончания поиска решения транспортной задачи.
Общая идея определения оптимального решения транспортной задачи методом потенциалов аналогична идее решения задачи линейного программирования симплекс-методом, а именно: сначала находят некоторое начальное допустимое решение транспортной задачи, а затем его последовательно улучшают до получения оптимального решения. В общем случае алгоритм метода потенциалов имеет итеративный характер и заключается в выполнении следующих действий:
1. Если исходная транспортная задача линейного программирования является открытой, то она преобразуется к замкнутому виду (2.1)- (2.5). С этой целью могут быть введены дополнительные переменные {xm+1,j}для фиктивного пункта производства am+1, если выполняется неравенство: или дополнительные переменные для фиктивного пункта потребления bn+1, если выполняется неравенство:
При этом дополнительным переменным должны соответствовать нулевые коэффициенты целевой функции: cm+1,1=cm+1,2=…=cm+1,n=0 или c1,n+1=c2,n+1=…=cm,n+1=0. Тем самым, с точностью до обозначений индексов переменных, в качестве исходной транспортной задачи будем рассматривать ее математическую модель в замкнутой форме (2.1)- (2.5).
2. Для транспортной задачи в замкнутой форме (2.1)-(2.5) находится некоторое начальное допустимое решение, которое записывается в специальную таблицу следующего вида таблица 2.2.
Рассмотрим особенности построение данной таблицы. Верхняя строка и левый столбец содержат искомые значения потенциалов, которые требуется отыскать на последующих этапах алгоритма, и значения правых частей ограничений (2.2)-(2.3).
Таблица 2.2. Общий вид таблицы метода потенциалов
| F(x) |
v1 b1 |
v2 b2 |
…. |
vn bn |
| u1 a1 |
c11 x11 |
c12 x12 |
… |
c1n x1n |
| u2 a2 |
c12 x12 |
c22 x22 |
c2n x2n |
|
| … |
… |
… |
… |
… |
| um am |
cm1 xm1 |
cm2 xm2 |
… |
cmn xmn |
В каждой ячейке таблицы содержится два значения: cij- стоимость транспортировки единицы продукта из i–го пункта производства в j–й пункт потребления и xij - значения переменных начального допустимого решения. При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ячейка называется занятой. Самая верхняя слева ячейка исходной таблицы содержит значение целевой функции (1) для содержащегося в таблице промежуточного решения. При этом значение целевой функции рассчитывается по формуле: F(x)=c11x11+c12x12+…+cnmxnm, где хij-ненулевые элементы таблицы 2.2, соответствующие переменным решаемой задачи.
Следует заметить, что первые два этапа метода потенциалов является подготовительными. Все последующие действия имеют итеративный повторяющийся характер и выполняются в рамках построенной исходной таблицы.
3. Для построенной таблицы 2 находятся значения потенциалов пунктов производства и потребления: v1, v2,… vn, u1,u2,…um. С этой целью составляется и решается следующая система линейных уравнений:
(2.10)
где индексы i и j соответствуют только ненулевым значениям переменных xij или занятым ячейкам таблицы 2.2. Как не трудно заметить, существование решения системы уравнений (2.10) обеспечивает выполнение второй группы условий критерия оптимальности (2.9). Для удобства найденные значения записываются в таблицу 2.2.
4. Для найденного решения системы уравнений (2.1) проверяется первая группа условий (2.8) критерия оптимальности. С этой целью вначале рассчитываются оценки свободных ячеек таблицы 2 по следующей формуле:
(2.11)
где индексы i и j соответствуют только нулевым значениям переменных xij или занятым ячейкам таблицы 2.2. В этом случае проверка первой группы условий критерия оптимальности найденного решения сводится к проверке следующего условия только для ячеек:
(2.12)
Если условие (2.12) выполняется, то найденное решения является оптимальным, и на этом дальнейшие расчеты могут быть завершены. Если же условие (2.12) не выполняется, то следует перейти к выполнению следующего этапа алгоритма метода потенциалов.
Из всех выбирается наименьшее значение (если их несколько- то любое из них). Соответствующая свободная ячейка помечается знаком (+), и для нее в таблице метода потенциалов строится цикл. При этом циклом в таблице метода потенциалов называется ломаная, вершины которой расположены в занятых ячейках таблицы, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. При правильном построении таблицы допустимого решение для любой свободной ячейки можно построить лишь один цикл.
5. После того как построен цикл для выбранной свободной ячейки, следует рассчитать значения переменных нового допустимого решения. Для этого необходимо изменить значение переменных предыдущего допустимого решения в пределах ячеек, связанных с данной свободной ячейкой. Это изменение производят по следующим правилам:
· каждой ячейки, принадлежащей построенному циклу от выбранной свободной ячейки, приписывают определенный знак, причем свободной клетке – знак (+), а всем остальным клеткам – поочередно (+) и (-). Соответствующие ячейки называют также минусовыми и плюсовыми;
· в выбранную свободную ячейку записывают меньшее из чисел хij, стоящих в минусовых ячейках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых ячейках, и вычитают из чисел, стоящих в минусовых ячейках таблицы. При этом ячейка, которая ранее была свободной, становится занятой, а минусовая ячейка, в которой стояло минимальное из чисел хij , считается свободной.
В результате указанного изменения значений переменных в пределах ячеек, связанных циклом с данной свободной ячейкой, находится новое допустимое решение транспортной задачи, которому соответствует меньшее по сравнению с предыдущим решением значение целев
Рассмотренный алгоритм метода потенциалов может быть изображен графически в форме диаграммы деятельности языка UML.
В заключении следует отметить, что при определении начального допустимого решения или в процессе решения задачи может быть получено вырожденное решение. Чтобы избежать в этом случае зацикливания алгоритма, следует соответствующие нулевые элементы допустимого решения заменить сколь угодно малым положительным числом ε, после чего решать задачу как невырожденную. В оптимальном решении такой задачи необходимо считать ε равным нулю.
Для нахождения исходного допустимого решения транспортной задачи на этапе 2 алгоритма может быть использован так называемый метод минимального элемента. Сущность этого метода состоит в том, что начальное допустимое решение находится за п+т-1 шагов. При этом на каждом шаге находится значение только одной переменной хij, которая записывается в соответствующую ячейку. После чего данная ячейка становится занятой. Первоначально все ячейки таблицы свободные и среди них отыскивается такая ячейка, которой соответствует минимальное значение из коэффициентов целевой функции сij .Если таких ячеек несколько, то следует выбрать любую из них. Для найденной свободной ячейки определяется значение соответствующей переменной: хij = min{ai , bj}.
Заполнение выбранной ячейки обеспечивает полностью либо удовлетворение потребности в пункте потребления, если хij = bj = min{ai , bj }, либо вывоз всех запасов из пункта производства, если хij = ai = min{ai , bj}.
В первом случае исключают из дальнейшего рассмотрения столбец таблицы, соответствующий bj , а для i-й строчки полагают новое значение .Во втором случае исключают из дальнейшего рассмотрения строку соответствующую ai, а для j-го столбца полагают новое значение .
После исключения строки или столбца из дальнейшего рассмотрения происходит нахождение среди свободных ячеек следующего минимального значения сij и заполнение найденной ячейки очередным значением переменной: хij = min{ai , bj } с соответствующим исключением строки или столбца. В итоге после п+т-1 шагов метод минимального элемента позволяет получить начальное допустимое решение закрытой транспортной задачи линейного программирования.
Проиллюстрируем использование рассмотренного алгоритма метода потенциалов для решения индивидуальной транспортной задачи (2.6) и (2.7). Поскольку исходная задача является закрытой, то выполнение действий этапа 1 рассмотренного алгоритма метода потенциалов не требуется.
Исходная таблица метода потенциалов, необходимая для нахождения начального допустимого решения задачи (2.5) и (2.7), будет иметь следующий вид таблица 2.3.
Для нахождения начального допустимого решения воспользуемся методом минимального элемента. Для этого в таблице 2.3 следует найти минимальное значение сij , которое равно 1. этому значению соответствует второй пункт производства и первый пункт потребления, при этом х21 = min{a2 , b1 }=14. Из дальнейшего рассмотрения следует исключить второй пункт производства, а для первого пункта потребления определить новое значение b’=b1-a1=15-14=1.
Таблица 2.3. Исходная таблица для нахождения
начального допустимого решения
| F(x) |
V1 15 |
V2 12 |
V3 8,5 |
V4 5,5 |
| u1 10 |
3 |
5 |
7 |
11 |
| u2 14 |
1 |
4 |
6 |
3 |
| u3 17 |
5 |
8 |
12 |
7 |
На следующем шаге метода минимального элемента в сокращенной таблице таблица 2.3 найдем минимальное значение сij , которое равно 3. Этому значению соответствует первый пункт производства и первый пункт потребления, при этом х11 = min{a1 , b1 }=1. Из дальнейшего рассмотрения следует исключить первый пункт потребления, а для первого пункта производства определить новое значение a’=a1-b1=10-1=9.
Поступая аналогичным образом, в результате будет получено начальное допустимое решение транспортной задачи (2.6) и (2.7), исходная таблица метода потенциалов которой будет иметь следующий вид таблица 2.4.
Таблица 2.4. Исходная таблица метода потенциалов
с начальным допустимым решением
| F(x) |
V1 15 |
V2 12 |
V3 8,5 |
V4 5,5 |
| u1 10 |
3 1 |
5 9 |
7 |
11 |
| u2 14 |
1 14 |
4 |
6 |
3 |
| U3 17 |
5 |
8 3 |
12 8,5 |
7 5,5 |
Непосредственной проверкой можно убедиться, что найденное начальное решение действительно является допустимым. Этому начальному решению соответствует значение целевой функции:
F(x)=3*1+1*14+5*9+8*3+12*8,5+7*5,5=226,5
После выполнения подготовительных этапов 1 и 2 метода потенциалов можно приступить к проверке условия получения оптимального решения (этап 3). Для этого необходимо найти потенциалы пунктов производства и потребления. Поскольку число заполненных ячеек исходной таблицы равно п+т-1=6, то искомая система должна содержать п+т=7 неизвестных для 6 уравнений. А именно, для определения значений потенциалов следует решить следующую систему уравнений: {v1+u1=3, v1+u2=1, v2+u1=5, v2+u3=8, v3+u3=12, v4+u3=7}, содержащую шесть уравнений с семью неизвестными. Поскольку число неизвестных превышает на единицу число уравнений, то одно из неизвестных можно положить равным произвольному числу, например v1=0. Далее можно найти последовательно из данной системы уравнений значения остальных неизвестных: v2=2, v3=6, v4=1, u1=3, u1=2, u3=6.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в исходную таблицу, которая на первой итерации алгоритма будет иметь следующий вид таблица 2.5.
Таблица 2.5. Таблица метода потенциалов
на первой итерации
| F(x) |
0 15 |
2 12 |
6 8,5 |
1 5,5 |
| 3 10 |
3 1 |
5 9 |
7 |
11 |
| 1 14 |
1 14 |
4 |
6 |
3 |
| 6 17 |
5 |
8 3 |
12 8,5 |
7 5,5 |
Для выполнения этапа 4 алгоритма по формуле (2.11)необходимо последовательно рассчитать значения оценок для свободных ячеек:
7-3-6=-2, 4-1-2=1,6-1-6=-1, 3-1-1=1, 5-6-0=-1. Поскольку среди оценок свободных ячеек имеются отрицательные, то условие (2.12) не выполняется, и найденное решение не является оптимальным, т.е. его можно улучшить.
Из всех выбирается наименьшее значение -2. Соответствующая свободная ячейка для помечается знаком (*), и для нее х13 в таблице метода потенциалов строится цикл содержащий занятые ячейки: х12, х32, х33. После этого следует перейти к выполнению действий этапа 5.
Таблица 2.6. Таблица метода потенциалов
после выполнения первой итерации
| F(x)=209,5 |
V1 15 |
V2 12 |
V3 8,5 |
V4 5,5 |
| u1 10 |
3 1 |
5 0,5(-) |
7 8,5(+) |
11 |
| u2 14 |
1 14 |
4 |
6 |
3 |
| U3 17 |
5 |
8 11,5(+) |
12 (-) |
7 5,5 |
Поскольку ячейка для х13 имеет знак (+), то соседние с ней в цикле занятые ячейки х12 и х33 будут иметь знак (-). Следуя по правилу чередования знаков, оставшаяся ячейка х32 будет иметь знак (+). Наименьшее из чисел в минусовых ячейках равно 8,5.
Ячейка х33 , в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно: , новое значение в плюсовой ячейке равно: .
В полученной таким образом новой таблице ячейка становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решение транспортной задачи с лучшим значением целевой функции F(x)=209.5. Этому допустимому решению соответствует новая таблица метода потенциалов, которая имеет следующий вид, таблица 2.7.
После получения таблицы 2.7 следует приступить к проверке условия получения оптимального решения (вторая итерация, этап 3).
Таблица 2.7. Метода потенциалов на
второй итерации
| F(x)=209,5 |
0 15 |
2 12 |
4 8,5 |
1 5,5 |
| 3 10 |
3 1 |
5 0,5 |
7 8,5 |
11 |
| 1 14 |
1 14 |
4 |
6 |
3 |
| 6 17 |
5 |
8 11,5 |
12 |
7 5,5 |
Для этого предварительно необходимо найти новые потенциалы пунктов производства и потребления. Для определения значений потенциалов следует решить следующую систему уравнений: {v1+u1=3, v1+u2=1, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=2, v3=4 v4=1, u1=3, u2=1 u3=6.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на второй итерации алгоритма будет иметь следующий вид, таблица 2.7.
Для выполнения этапа 4 на второй итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения для свободных ячеек: 11-3-1=-7, 4-1-2=1,6-1-4=1, 3-1-1=1, 5-6-0=-1, 12-6-4=2.
Поскольку среди оценок свободных ячеек имеется единственная отрицательная, то условие (2.12) не выполняется, и найденное решение не является оптимальным, т.е. его можно улучшить. Для единственного значения соответствующая свободная ячейка для х31 помечается знаком (+), и для нее в таблице метода потенциалов строится цикл, содержащий занятые ячейки: х11, х12,х32. После этого следует перейти к выполнению действий этапа 5 второй итерации.
На этапе 5 необходимо определить плюсовые и минусовые ячейки. Поскольку ячейка для х31 имеет знак (+), то соседние с ней в цикле занятые ячейки х11 и х32 будут иметь знак (-). Следуя правилу чередования знаков, оставшаяся ячейка х12, будет иметь знак (+). Наименьшее из чисел в минусовых ячейках равно 1. Ячейка х11, в которой находится это число, становится свободной в новой таблице метода потенциалов. Другие значения ячеек цикла в новой таблице получаются следующим образом: новое значение в минусовой ячейке равно: x’32=x32-1=10.5, а новое значение в плюсовой ячейке равно: x’12=x12+1=1,5. В полученной таким образом новой таблице ячейка x’31=0 становится свободной. После выполненных на этапе 5 преобразований получаем новое допустимое решения транспортной задачи с лучшим значением целевой функции F(x)= 208.5. Этому допустимому решению соответствует новая таблица методов потенциалов, которая имеет следующий вид, таблица 2.8.
После получения таблицы 8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3). Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5. На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 9.
После получения таблицы 2.8 следует снова проверить условия получения оптимального решения (третья итерация, этап 3).
Для этого необходимо найти новые потенциалы пунктов производства и потребления, т. е. решить следующую систему уравнений: {v1+u2=1, v1+u3=5, v2+u1=5, v2+u3=8, v3+u1=7, v4+u3=7}. Полагая v1=0, находятся значения остальных неизвестных: v2=3, v3=5 v4=2, u1=2, u2=1 u3=5.
На этом действия этапа 3 заканчиваются, а найденные значения потенциалов записываются в таблицу, которая на третьей итерации алгоритма будет иметь следующий вид , таблица 2.9.
Таблица 2.8. Таблица метода потенциалов
после выполнения второй итерации
| F(x)=209,5 |
V1 15 |
V2 12 |
V3 8,5 |
V4 5,5 |
| u1 10 |
3 (-) |
5 1,5(-) |
7 8,5 |
11 |
| u2 14 |
1 14 |
4 |
6 |
3 |
| U3 17 |
5 1(+) |
8 10,5(-) |
12 |
7 5,5 |
Для выполнения этапа 4 на третьей итерации алгоритма по формуле (2.11) необходимо последовательно рассчитать значения оценок для свободных ячеек: 3-2-0=1, 11-2-2=7,4-1-3=0, 6-1-5=0, 3-1-2=0, 12-5-5=2. Поскольку среди оценок свободных ячеек отсутствуют отрицательные значения, то условие (2.12) выполняется, и найденное решение является оптимальным.
Таблица 2.9. Таблица метода потенциалов
на третьей итерации
| F(x)=209,5 |
0 15 |
3 12 |
5 8,5 |
2 5,5 |
| 2 10 |
3 |
5 1,5 |
7 8,5 |
11 |
| 1 14 |
1 14 |
4 |
6 |
3 |
| 5 17 |
5 1 |
8 10,5 |
12 |
7 5,5 |
Таким образом, искомое оптимальное решение исходной транспортной задачи, полученное с использованием описанного алгоритма метода потенциалов, содержится в таблице9 и равно: х12=1,5, х13=8,5, х21=14, х31=1, х32=10,5, х34=5,5, значения остальных переменных равны 0. Оптимальное значение целевой функции при этом равно: F(x)=208.5.
Сравнение найденных оптимальных решений транспортной задачи с помощью программы MS Excel и метода потенциалов показывает их полное совпадение, что может свидетельствовать о достоверности соответствующих результатов.
2.4 Рекомендации по решению задач оптимизации с
помощью надстройки Поиск решения.
Построение математической модели задачи.
Работа по решению некоторой оптимизационной задачи всегда начинается с построения математической модели, для чего необходимо ответить на следующие вопросы:
- Каковы переменные модели (для определения каких величин строится модель)?
- В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?
- Каким ограничениям должны удовлетворять неизвестные?
Стоит также учесть, что при конструировании модели формулировка ограничений является самой ответственной частью конструкции. В некоторых случаях ограничения очевидны, например, ограничение на количество сырья. Другие же ограничения могут быть менее очевидны и могут быть указаны неверно. Например:
- В модели с несколькими периодами времени величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода;
- В модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец период плюс количество отправленного;
- Многие величины в модели по своему физическому смыслу не могут быть отрицательными, например, количество полученных единиц товара.
Таким образом, на данном этапе делаются выводы об исходных данных (детерминировать или случайные), искомых переменных (непрерывные или дискретные), о пределах, в которых могут находиться значения искомых величин, о зависимостях между переменными (линейные или нелинейные), о критериях, по которым необходимо находить оптимальное решение. Сюда же входит преодоление несовместимости, а также неограниченности целевой функции: при максимизации целевой функции область допустимых решений должна быть ограничена сверху, при минимизации - ограничена снизу.
Решение задач с помощью надстройки Поиск решения.
Прежде всего подготовьте рабочий лист MS Excel-корректно разместите на нем все исходные данные, грамотно введите необходимые формулы для целевой функции и для других зависимостей, выберите место для значений переменных.
Правильно выберите все ограничения, переменные, целевую функцию и другие значения в окно Поиск решения.
Большую часть задач оптимизации представляют собой задачи линейного программирования, т.е. такие, у которых критерий оптимизации и ограничения- линейные функции. В этом случае для решения задачи следует установить флажок Линейная модель
в окне Параметры поиска решения.
Это обеспечит применение симплекс-метода. В противном случае даже для решения линейной задачи будут использованы более общие (т.е. более медленные)методы.
Поиск решения может работать также и с нелинейными зависимостями и ограничениями. Это, как правило, задачи нелинейного программирования или, например, решение системы нелинейных уравнений. Для успешной работы средства Поиск решения следует стремиться к тому, чтобы зависимости были гладкими или, по крайней мере, непрерывными. Наиболее часто разрывные зависимости возникают при использовании функции ЕСЛИ(), среди аргументов которой имеются переменные величины модели. Проблемы могут возникнуть также и при использовании в модели функций типа ABS(), ОКРУГЛ() и т.д.
Решая задачи с нелинейными зависимостями, следует:
- Ввести предварительно предположительные значения искомых переменных (иногда легко получить графическое представление решение и сделать приблизительные выводы о решении).
- В окне Параметры поиска снять (если установлен) флажок Линейная модель.
Решая задачи целочисленного программирования, не следует забывать также о требованиях целочисленности и булевости.
Анализ решения задачи оптимизации.
При необходимости анализ решения. Часто добавляется также представление в виде графиков или диаграмм. Можно получить и отчет о поиске решения.
Отчеты бывают трех типов: Результаты, Устойчивость, Пределы.
Тип отчета выбирается по окончании поиска решения в окне Результаты поиска решения в списке Тип отчета (можно выбрать сразу два или три типа).
- Отчет типа Результаты содержит окончательные значения параметров задачи целевой функции и ограничений.
- Отчет типа Устойчивость показывает результаты малых изменений параметров поиска решения.
- Отчет типа Пределы показывает изменения решения при поочередной максимизации и минимизации каждой переменной при неизменных других переменных.
Линейная оптимизация.
Линейное программирование-это раздел математического программирования, посвященный нахождению экстремума линейных функций нескольких переменных при дополнительных линейных ограничениях, которые налагаются на переменные. Методы, с помощью которых решаются задачи, подразделяются на универсальные (например, симплексный метод) и специальные. С помощью универсальных методов решаются любые задачи линейного программирования. Особенностью задач линейного программирования является то, что экстремум целевой функции достигается на границе области допустимых решений.
Пример. Планирование производства материалов.
Фирма выпускает два типа строительных материалов: А и В. продукция обоих видов поступает в продажу. Для производства материалов используются два исходных продукта:1 и 2. Максимально возможные суточные запасы этих продуктов составляют 7 и 9 тонн соответственно. Расходы продуктов 1 и 2 на 1 тонну соответствующих материалов приведены в табл. 7.4.
Изучение рынка сбыта показало, что суточный спрос на материал В никогда не превышает спроса на материал А более чем на 1 тонну. Кроме того, спрос на материал А никогда не превышает 3 тонн в сутки. Оптовые цены одной тонны материалов равны: 4000 у.е. для В и 3000 у.е. для А. Какое количество материала каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?
Таблица 2.10. Расход продуктов
| Исходный продукт |
Расход исходных продуктов, т (на одну тонну материалов) |
Максимально Возможный запас, т |
|
| Материл А |
Материал В |
||
| 1 |
3 |
2 |
7 |
| 2 |
2 |
3 |
9 |
Решение
1. Формулировка математической задачи:
· переменные для решения задачи: х1- суточный объём производства материала А, х2- суточный объём производства материала В;
· определение функции цели (критерия оптимизации). Суммарная суточная прибыль от производства х1 материала А и х2 материала В равна:
F=4000x2+3000x1
поэтому цель фабрики- среди всех допустимых значений х2 и х1 найти такие, которые максимизируют суммарную прибыль от производства материалов F:
F=4000x2+3000x1-max;
· ограничения на переменные:
- объём производства красок не может быть отрицательным, т.е.
х20, х10;
- расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т.е.:
2х2+3х17,
3х2+2х19,
- ограничения на величину спроса на материалы:
х1-х21,
х13,
· Найти максимум следующей функции:
F=4000x2+3000x1-max,
· При ограничениях вида:
2х2+3х17,
3х2+2х19,
х1-х21,
х13,
х20, х10;
2.Подготовка листа рабочей книги MS Excel для вычислений- на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7.3. Переменные задачи х1 и х2 находятся, соответственно, в ячейках С3 и С4. Целевая функция находится в ячейке С6 и содержит формулу:
=4000*С4+3000*С3.
Ограничения на задачу учтены в ячейках С8:D11.
Рисунок 2. Рабочий лист MS Excel для решения задачи
планирования производства материалов
3.Работа с надстройкой Поиск решения- воспользовавшись командой Сервис Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рисунке 2). Результат работы по поиску решения помещен на рисунке 2
Рисунок 2. Установка необходимых параметров задачи
планирования материалов в окне Поиск решения
Рисунок 2. Результат расчета надстройки Поиск решения
Рисунок 2. Отчета по результатам Поиска решения
Описание отчетов о решении задачи
- Отчет по результатам –таблица Целевая ячейка выводит сведения о целевой функции; таблица Изменяемые ячейки показывает значение искомых переменных, полученных в результате решения задачи; таблица Ограничения отображает результаты оптимального решения для ограничений и для граничных условий. В поле Формула приведены зависимости, которые были введены в окно Поиск решения, в поле Разница- величина использованного материала. Если материал используется полностью, то в поле Статус указывается связанное, при неполном использовании материала в этом поле указывается не связан. Для граничных условий приводятся аналогичные величины с той лишь разницей, что вместо величины с той лишь разницей, что вместо величины неиспользованного продукта показана разность между значением переменой в найденном оптимальном решении и заданным для неё граничным условием.
- Отчет по устойчивости –в таблице Изменяемые ячейки приводится результат решения задачи.
В таблице Ограничения выводятся значения для ограничений, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.
Рисунок 2. Отчет по устойчивости Поиска решения
- Отчет по пределам- в отчете показано, в каких пределах может изменяться количество материалов, вошедших в оптимальное решение, при сохранении структуры оптимального решения; приводятся значение переменных в оптимальном решение, а также нижние и верхние пределы изменения значений переменных; здесь также указаны значения целевой функции при выпуске данного типа продукции на верхнем и нижнем пределах.
Глава
III
Двойственная задача линейного программирования
3.1 Математическая формулировка двойственной задачи
линейного программирования
В общем случае двойственной по отношению к стандартной задаче линейного программирования (1.6) и (1.7) называется такая задача линейного программирования, которая может быть записана в следующем виде:
b1y1+b2y2+,…,+bmym → (3.1)
где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:
(3.2)
и y1,y2,,…,yn0.
Как не трудно заметить, количество переменных двойственной задаче линейного программирования равно количеству ограничений стандартной задачи, а количество ограничений двойственной задачи равно количеству переменных стандартной задачи линейного программирования. При этом, если исходная задача формулируется как задача максимизации целевой функции, то двойственная- как задача минимизации и наоборот. Аналогично изменяются и знаки ограничений двойственной задачи по отношению к исходной задаче линейного программирования.
Существует важная взаимосвязь между двойственной и стандартной задачами линейного программирования. А именно, если одна из задач (1.6) и (1.7) или (3.1) и (3.2) имеет оптимальное решение, то и двойственная ей задача линейного программирования имеет оптимальное решение, при этом оптимальные значения соответствующих целевых функций двойственных задач имеют равные значения, т.е. f’op=fopt , где f’(y)- целевая функция в выражении (3.1), а f(x)–целевая функция в выражении (1.6). Если же для одной из задач (1.6) и (1.7) или (3.1) и (3.2) целевая функция не ограничена на допустимом множестве альтернатив, то соответствующая ей двойственная задача линейного программирования не имеет решения, т.е. имеет множество допустимых альтернатив. Наконец, если одна из задач (1.6) и (1.7) или (3.1) и (3.2) имеет пустое множество допустимых альтернатив, то соответствующая ей двойственная задача линейного программирования либо имеет неограниченную целевую функцию, либо пустое множество допустимых альтернатив.
В общем случае совместное рассмотрение пары двойственных задач линейного программирования позволяет не только выполнить качественный анализ их решения, но и практически использовать найденное решение одной из них для более простого решения другой задачи. Хотя данное свойство оказывается полезным, главным образом, при выполнении ручных расчетов, далее рассмотрим процесс решения двойственных задач линейного программирования с помощью программы MS Excel применительно к задаче о красках.
3.2 Математическая постановка двойственной задачи о красках
Напомним, что исходная постановка задачи о красках сформулирована в форме (3.1) и (3.2). двойственная к ней задача линейного программирования после выполнения простейших преобразований с целью получения целочисленных коэффициентов целевой функции и ограничений может быть записана в следующем виде:
100y1+70y2+100y3→ (3.3)
где множество допустимых альтернатив формируется следующей системой ограничений типа:
(3.4)
и y1,y2,y30.
3.3 Решение двойственной задачи о красках
с помощью MS Exsel
Для решения двойственной задачи о производстве красок с помощью программы MS Exsel создадим новый рабочий лист с именем Двойственная задача. Далее необходимо выполнить следующие действия:
1. Внесем необходимые записи в ячейки А1:Е1, А2:А6, Е4:F4. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решение рассматриваемой двойственной задачи линейного программирования.
2. В ячейки B2:D3 введем значения коэффициентов целевой функции (3.3) b1=10, b2=7, b3=5.
3. В ячейку E2 введем формулу: =суммпроизв(В2:D2; B3:D3), которая представляет целевую функцию (3.3).
4. В ячейки B5:D6 введем значения коэффициентов ограничений (3.4.).
5. В ячейки F5:F6 введем значения правых значений ограничений (3.4.).
В ячейку E5 введем формулу: =суммпроизв($В$2:$D$2; B5:D5), которая представляет левую часть первого ограничения (3.4).
Рисунок 3.1 Исходные данные для решения двойственной
|
задачи о производстве красок
7. Скопируем формулу, введенную в ячейку Е5, в ячейку Е6.
Внешний вид рабочего листа MS Office Excel 2003 с исходными данными для решения задачи об оптимальном рационе питания имеет следующий вид рисунок 3.1.
Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис|Поиск решения.
После появления диалогового окна Поиск решения следует выполнить следующие действия:
1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $Е$2.
2. Для группы Равной: выбрать вариант поиска решения- минимальному значению.
3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $В$2:$D$2.
4. Добавить три ограничения, соответствующие (3.5), и одно ограничение на допустимые значения переменных.
5. В дополнительном окне параметров поиска решения следует выбрать отметки Линейная модель и Неотрицательные значения рисунок 3.2.
Рисунок 3.2. Ограничения на значения переменных и параметры мастера поиска решения для двойственной задачи о красках
После задания ограничений и целевой функции можно приступить к поиску численного решения, для чего следует нажать Выполнить. После выполнения расчетов программой MS Excel будет получено количественное решение, которое имеет следующий вид рисунок 3.3.
Рисунок 3.3 Результат количественного решения
двойственной задачи о красках
Рисунок 3.4. Отчет по результатам
Результатом решения двойственной задачи о производстве красок являются найденные оптимальные значения двойственных переменных: у1=70, у2=90, у3=0,которымсоответствует значение целевой функции: f’opt=13 300. При выполнении расчетов для ячеек был выбран числовой формат с тремя знаками после запятой.
Одним из наиболее важных свойств двойственных задач является наличие в симплекс-таблице, соответствующей оптимальному решению одной из них, значений оптимального решения двойственной задачи. Применительно к задаче о красках, значения оптимального решения двойственной задачи о красках (3.3) и (3.4) можно сразу получить из последней симплекс-таблицы. А именно, оптимальное решение двойственной задачи содержится в индексной строке в столбцах, соответствующих дополнительным переменным х3,х4,х5.поскольку переменная х3 вводится в первое ограничение прямой задачи, которому, в свою очередь, соответствует первая переменная у1 двойственной задачи, то из табл. непосредственно следует оптимальное значение для у1=хf3=70.
Аналогично могут быть получены и значения у2=хf4=90 и у3=хf5=0. При этом нет никакой необходимости в непосредственном решении двойственной задачи.
Экономическая интерпретация полученных решений прямой задачи двойственной задач заключается в следующем. Решение прямой задачи о красках (4.3.1) и (4.3.2) дает оптимальный план производства красок первого и второго вида. Решение двойственной задачи о красках (3.3) и (3.4)- оптимальную систему оценок типов сырья, используемого для производства этих красок. При этом выполняются следующие условия. Если некоторый тип сырья используется полностью, то соответствующая этому типу двойственная переменная в оптимальном решении двойственной задачи будет иметь положительное значение. Если же некоторый тип сырья используется не полностью, то соответствующая этому типу двойственная переменная в оптимальном решении двойственной задачи будет равняется нулю.
Применительно к паре решенных двойственных задач (4.3.1) и (4.3.2) и (3.3) и (3.4) первые два неравенства прямой задачи (4.3.2) превращаются в равенства, откуда следует, что запасы индиго и железного купороса используются полностью. Об этом свидетельствуют и оптимальные значения двойственных переменных: у1=70, у2=90. Напротив, запасы свежегашеной извести используются не полностью, что согласуется со значением третьей двойственной переменной найденного оптимального решения у3=0.
Для целей экономического анализа модели задачи линейного программирования удобно предположить, что двойственные переменные могут выступать в роли оценок типов сырья, используемого в производстве красок. Более того, величина данной двойственной оценки показывает, на сколько возрастет максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего типа на 1кг.
Таким образом, двойственные оценки могут быть использованы для определения степени дефицитности типов сырья для производства продукции. В связи с этим анализ оптимальных решений прямой и двойственных задач линейного программирования становится необходимым этапом экономического анализа эффективного планирования производства продукции.
Список литературы
1. Леоненков А. Решение задач оптимизации в среде MS Excel –СПб..БХВ- Петербург, 2005.- 704 с.. ил.
2. Сдвинков О.А. математика в MS Excel 2002- М… Солон-Пресс, 2004-192 с.. ил.
3. Калихман И.Л. Сборник задач по математическому программированию. Изд. 2-е, доп. И перераб. М., “Высшая школа”, 1975.-270 с.
4. Шапкин А.С., Мазаева Н.П. Математичаские методы и модели исследования операций: Учебник.- М.. Издательско-торговая корпорация “Дашков и К°”, 2003.
5. Банди Б. Методы оптимизации. Вводный курс –М.. Радио и связь, 1988.-128 с.
6. Гаас С. Линейное программирование.- М… ГИМФМЛ, 1961-304 с.
7. Гилл Ф., Мюррей У., Райт М. Практическая оптимиация. – М.. Мир, 1985.- 512 с.
8. Заславский Ю.Л. Сборник задач по линейному программированию.- М.. Наука, 1969.- 256.
9. Калихман И.Л. Сборник задач по линейной алгебре и программированию.- М.. Высшая школа, 1969.-160 с.