Решение транспортной задачи линейного программирования в среде MS Excel
В полученной
таким образом
новой таблице
ячейка
становится
свободной.
После выполненных
на этапе 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- суточный объём производства материала А, х2- суточный объём производства материала В;
определение функции цели (критерия оптимизации). Суммарная суточная прибыль от производства х1 материала А и х2 материала В равна:
F=4000x2+3000x1
поэтому цель фабрики- среди всех допустимых значений х2 и х1 найти такие, которые максимизируют суммарную прибыль от производства материалов F:
F=4000x2+3000x1аmax;
ограничения на переменные:
объём производства красок не может быть отрицательным, т.е.
х2
0,
х1
0;
расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т.е.:
2х2+3х1
7,
3х2+2х1
9,
ограничения на величину спроса на материалы:
х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. Отчета по результатам Поиска решения

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

Глава 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.1) и (3.2). двойственная к ней задача линейного программирования после выполнения простейших преобразований с целью получения целочисленных коэффициентов целевой функции и ограничений может быть записана в следующем виде:
100y1+70y2+100y3→
(3.3)
где множество
допустимых
альтернатив
формируется
следующей
системой ограничений
типа:
(3.4)
и y1,y2,y3
0.
3.3 Решение двойственной задачи о красках
с помощью MS Exsel
Для решения двойственной задачи о производстве красок с помощью программы MS Exsel создадим новый рабочий лист с именем Двойственная задача. Далее необходимо выполнить следующие действия:
Внесем необходимые записи в ячейки А1:Е1, А2:А6, Е4:F4. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решение рассматриваемой двойственной задачи линейного программирования.
В ячейки B2:D3 введем значения коэффициентов целевой функции (3.3) b1=10, b2=7, b3=5.
В ячейку E2 введем формулу: =суммпроизв(В2:D2; B3:D3), которая представляет целевую функцию (3.3).
В ячейки B5:D6 введем значения коэффициентов ограничений (3.4.).
В ячейки F5:F6 введем значения правых значений ограничений (3.4.).
В ячейку E5 введем формулу: =суммпроизв($В$2:$D$2; B5:D5), которая представляет левую часть первого ограничения (3.4).
Рисунок 3.1 Исходные данные для решения двойственной
задачи
о производстве
красок
7. Скопируем формулу, введенную в ячейку Е5, в ячейку Е6.
Внешний вид рабочего листа MS Office Excel 2003 с исходными данными для решения задачи об оптимальном рационе питания имеет следующий вид рисунок 3.1.
Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню: Сервис|Поиск решения.
После появления диалогового окна Поиск решения следует выполнить следующие действия:
В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $Е$2.
Для группы Равной: выбрать вариант поиска решения- минимальному значению.
В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $В$2:$D$2.
Добавить три ограничения, соответствующие (3.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кг.
Таким образом, двойственные оценки могут быть использованы для определения степени дефицитности типов сырья для производства продукции.