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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН
КАЗАХСКИЙ ГОСУДАРСТВЕННЫЙ ЖЕНСКИЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ
КАФЕДРА ИНФОРМАТИКИДипломная работаПОТЕМЕ:«Решение транспортнойзадачи линейного программирования в среде MSExcel»

Выполнила: студентка 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) не является противоречивой, однакосоответствующая ей область пространства Rn является неограниченной. В этом случаезадача линейного программирования не имеет решения, в случае, если линейнаяфункция (1.6) не ограничена в неограниченной области, соответствующей множествудопустимых альтернатив />.
3.        Система ограничений (1.7) не является противоречивой, и при этомсоответствующая ей область пространства Rn является ограниченной. В этом случаезадача линейного программирования имеет решения.
В последней ситуации задача линейного программирования может иметьлибо единственное решение, либо континуум решений. Континуум решений имеетместо в том случае, когда линейная целевая функция оказывается параллельнойфункции левой части одного из ограничений.

ГЛАВА 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) для удобства используются переменные с двумя индексами.
При этом общее число переменных транспортной задачи равно: m/>n, чтоделает возможным сформулировать эквивалентную математическую постановкутранспортной задачи с одноиндексными переменными.
Классическая транспортная задача линейного программирования являетсясбалансированной или закрытой, т.е. формулируется в форме, когда имеет месторавенство общего объема производства рассматриваемого продукта общему объемуего потребления. Этому условию соответствует отдельное ограничение (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, считается свободной.
В результате указанного изменения значенийпеременных в пределах ячеек, связанных циклом с данной свободной ячейкой,находится новое допустимое решение транспортной задачи, которому соответствуетменьшее по сравнению с предыдущим решением значение целевой функции. Послеполучения новой таблицы метода потенциалов следует прейти к выполнению действийэтапа 3 настоящего алгоритма.
Рассмотренный алгоритм метода потенциаловможет быть изображен графически в форме диаграммы деятельности языка 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)
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
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
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 Рекомендации по решению задач оптимизации с
помощью надстройки Поиск решения.
Построение математической модели задачи.
Работа по решению некоторой оптимизационнойзадачи всегда начинается с построения математической модели, для чегонеобходимо ответить на следующие вопросы:
q  Каковы переменные модели (для определения каких величин строитсямодель)?
q  В чем состоит цель, для достижения которой из множества всех допустимыхзначений переменных выбираются оптимальные?
q  Каким ограничениям должны удовлетворять неизвестные?
Стоит также учесть, что приконструировании модели формулировка ограничений является самой ответственнойчастью конструкции. В некоторых случаях ограничения очевидны, например,ограничение на количество сырья. Другие же ограничения могут быть менееочевидны и могут быть указаны неверно. Например:
q  В модели с несколькими периодами времени величина материальногоресурса на начало следующего периода должна равняться величине этого ресурса наконец предыдущего периода;
q  В модели поставок величина запаса на начало периода плюсколичество полученного должна равняться величине запаса на конец период плюсколичество отправленного;
q  Многие величины в модели по своему физическому смыслу не могутбыть отрицательными, например, количество полученных единиц товара.
Таким образом, на данном этапе делаютсявыводы об исходных данных (детерминировать или случайные), искомых переменных(непрерывные или дискретные), о пределах, в которых могут находиться значенияискомых величин, о зависимостях между переменными (линейные или нелинейные), окритериях, по которым необходимо находить оптимальное решение. Сюда же входитпреодоление несовместимости, а также неограниченности целевой функции: примаксимизации целевой функции область допустимых решений должна быть ограниченасверху, при минимизации — ограничена снизу.Решениезадач с помощью надстройки Поиск решения.
Прежде всего подготовьте рабочий лист MS Excel-корректно разместите на немвсе исходные данные, грамотно введите необходимые формулы для целевой функции идля других зависимостей, выберите место для значений переменных.
Правильно выберите все ограничения, переменные, целевую функцию идругие значения в окно Поиск решения.
Большую часть задач оптимизации представляют собой задачилинейного программирования, т.е. такие, у которых критерий оптимизации иограничения- линейные функции. В этом случае для решения задачи следуетустановить флажок Линейная модель в окне Параметры поиска решения. Этообеспечит применение симплекс-метода. В противном случае даже для решениялинейной задачи будут использованы более общие (т.е. более медленные)методы.
Поиск решения может работать также и с нелинейными зависимостями иограничениями. Это, как правило, задачи нелинейного программирования или,например, решение системы нелинейных уравнений. Для успешной работы средства Поискрешения следует стремиться к тому, чтобы зависимости были гладкими или, покрайней мере, непрерывными. Наиболее часто разрывные зависимости возникают прииспользовании функции ЕСЛИ(), среди аргументов которой имеются переменныевеличины модели. Проблемы могут возникнуть также и при использовании в моделифункций типа ABS(), ОКРУГЛ() и т.д.
Решая задачи с нелинейными зависимостями, следует:
q Ввести предварительно предположительные значения искомыхпеременных (иногда легко получить графическое представление решение и сделатьприблизительные выводы о решении).
q В окне Параметры поиска снять (если установлен) флажок Линейнаямодель.
Решая задачи целочисленного программирования, не следует забыватьтакже о требованиях целочисленности и булевости.
Анализ решения задачи оптимизации.
При необходимости анализ решения. Частодобавляется также представление в виде графиков или диаграмм. Можно получить иотчет о поиске решения.
Отчеты бывают трех типов: Результаты,Устойчивость, Пределы.
Тип отчета выбирается по окончании поискарешения в окне Результаты поиска решения в списке Тип отчета (можно выбратьсразу два или три типа).
q  Отчеттипа Результаты содержит окончательные значения параметров задачи целевойфункции и ограничений.
q  Отчеттипа Устойчивость показывает результаты малых изменений параметров поискарешения.
q  Отчеттипа Пределы показывает изменения решения при поочередной максимизации иминимизации каждой переменной при неизменных других переменных.
Линейная оптимизация.
Линейное программирование-это разделматематического программирования, посвященный нахождению экстремума линейныхфункций нескольких переменных при дополнительных линейных ограничениях, которыеналагаются на переменные. Методы, с помощью которых решаются задачи,подразделяются на универсальные (например, симплексный метод) и специальные. Спомощью универсальных методов решаются любые задачи линейного программирования.Особенностью задач линейного программирования является то, что экстремумцелевой функции достигается на границе области допустимых решений.
Пример. Планирование производстваматериалов.
Фирма выпускает два типа строительных материалов:А и В. продукция обоих видов поступает в продажу. Для производства материаловиспользуются два исходных продукта: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;
·          ограничения на переменные:
q  объёмпроизводства красок не может быть отрицательным, т.е.
х2/>0, х1/>0;
q  расходисходного продукта для производства обоих видов материалов не можетпревосходить максимально возможного запаса данного исходного продукта, т.е.:
2х2+3х1/>7,
3х2+2х1/>9,
q  ограниченияна величину спроса на материалы:
х1-х2/>1,
х1/>3,
·          Найти максимум следующей функции:
F=4000x2+3000x1àmax,
·          При ограничениях вида:
2х2+3х1/>7,
3х2+2х1/>9,
х1-х2/>1,
х1/>3,
х2/>0, х1/>0;
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. Отчета по результатам Поиска решения
/>

Описание отчетов о решении задачи
q  Отчет по результатам–таблица Целеваяячейка выводит сведения о целевой функции; таблица Изменяемые ячейкипоказывает значение искомых переменных, полученных в результате решения задачи;таблица Ограниченияотображает результаты оптимального решения для ограничений и дляграничных условий. В поле Формула приведены зависимости, которые были введены вокно Поискрешения, в поле Разница- величина использованного материала. Еслиматериал используется полностью, то в поле Статус указывается связанное, принеполном использовании материала в этом поле указывается не связан. Дляграничных условий приводятся аналогичные величины с той лишь разницей, чтовместо величины с той лишь разницей, что вместо величины неиспользованногопродукта показана разность между значением переменой в найденном оптимальномрешении и заданным для неё граничным условием.
q  Отчет по устойчивости –втаблице Изменяемыеячейки приводится результат решения задачи.
В таблице Ограничения выводятся значения дляограничений, при которых сохраняется оптимальный набор переменных, входящих воптимальное решение.
/>Рисунок 2. Отчет поустойчивости Поиска решения
q  Отчет по пределам- вотчете показано, в каких пределах может изменяться количество материалов,вошедших в оптимальное решение, при сохранении структуры оптимального решения;приводятся значение переменных в оптимальном решение, а также нижниеи верхние пределы изменения значений переменных; здесь также указаны значенияцелевой функции при выпуске данного типа продукции на верхнем и нижнемпределах.

/>



Глава IIIДвойственная задачалинейного программирования
 3.1Математическая формулировка двойственной задачилинейногопрограммирования
 
В общем случае двойственной по отношению к стандартной задаче линейногопрограммирования (1.6) и (1.7) называется такая задача линейногопрограммирования, которая может быть записана в следующем виде:
b1y1+b2y2+,…,+bmym →/>(3.1)
где множество допустимых альтернатив /> формируется следующей системойограничений типа неравенств:
/> (3.2)
и y1,y2,,…,yn/>0.
Как не трудно заметить, количество переменных двойственной задачелинейного программирования равно количеству ограничений стандартной задачи, аколичество ограничений двойственной задачи равно количеству переменныхстандартной задачи линейного программирования. При этом, если исходная задачаформулируется как задача максимизации целевой функции, то двойственная- какзадача минимизации и наоборот. Аналогично изменяются и знаки ограниченийдвойственной задачи по отношению к исходной задаче линейного программирования.
Существует важная взаимосвязь между двойственной и стандартной задачамилинейного программирования. А именно, если одна из задач (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,y3/>0.
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 с.