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

(1.7)

и x1,x2…,,x n

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

с1х1+с2х2+…+с n x n ®

(1.8)

где множество допустимых альтернатив

формируется следующей системой ограничений типа неравенств:

(1.9)

и x1,x2…,,x n

При рассмотрении общих особенностей задачи линейного программирования удобной оказывается стандартная форма математической постановки задачи линейного программирования (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

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