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

- В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?

- Каким ограничениям должны удовлетворять неизвестные?

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

- В модели с несколькими периодами времени величина материального ресурса на начало следующего периода должна равняться величине этого ресурса на конец предыдущего периода;

- В модели поставок величина запаса на начало периода плюс количество полученного должна равняться величине запаса на конец период плюс количество отправленного;

- Многие величины в модели по своему физическому смыслу не могут быть отрицательными, например, количество полученных единиц товара.

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

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

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

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

Большую часть задач оптимизации представляют собой задачи линейного программирования, т.е. такие, у которых критерий оптимизации и ограничения- линейные функции. В этом случае для решения задачи следует установить флажок Линейная модель в окне Параметры поиска решения. Это обеспечит применение симплекс-метода. В противном случае даже для решения линейной задачи будут использованы более общие (т.е. более медленные)методы.

Поиск решения может работать также и с нелинейными зависимостями и ограничениями. Это, как правило, задачи нелинейного программирования или, например, решение системы нелинейных уравнений. Для успешной работы средства Поиск решения следует стремиться к тому, чтобы зависимости были гладкими или, по крайней мере, непрерывными. Наиболее часто разрывные зависимости возникают при использовании функции ЕСЛИ(), среди аргументов которой имеются переменные величины модели. Проблемы могут возникнуть также и при использовании в модели функций типа ABS(), ОКРУГЛ() и т.д.

Решая задачи с нелинейными зависимостями, следует:

- Ввести предварительно предположительные значения искомых переменных (иногда легко получить графическое представление решение и сделать приблизительные выводы о решении).

- В окне Параметры поиска снять (если установлен) флажок Линейная модель.

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

Анализ решения задачи оптимизации.

При необходимости анализ решения. Часто добавляется также представление в виде графиков или диаграмм. Можно получить и отчет о поиске решения.

Отчеты бывают трех типов: Результаты, Устойчивость, Пределы.

Тип отчета выбирается по окончании поиска решения в окне Результаты поиска решения в списке Тип отчета (можно выбрать сразу два или три типа).

- Отчет типа Результаты содержит окончательные значения параметров задачи целевой функции и ограничений.

- Отчет типа Устойчивость показывает результаты малых изменений параметров поиска решения.

- Отчет типа Пределы показывает изменения решения при поочередной максимизации и минимизации каждой переменной при неизменных других переменных.

Линейная оптимизация.

Линейное программирование-это раздел математического программирования, посвященный нахождению экстремума линейных функций нескольких переменных при дополнительных линейных ограничениях, которые налагаются на переменные. Методы, с помощью которых решаются задачи, подразделяются на универсальные (например, симплексный метод) и специальные. С помощью универсальных методов решаются любые задачи линейного программирования. Особенностью задач линейного программирования является то, что экстремум целевой функции достигается на границе области допустимых решений.

Пример. Планирование производства материалов.

Фирма выпускает два типа строительных материалов: А и В. продукция обоих видов поступает в продажу. Для производства материалов используются два исходных продукта:1 и 2. Максимально возможные суточные запасы этих продуктов составляют 7 и 9 тонн соответственно. Расходы продуктов 1 и 2 на 1 тонну соответствующих материалов приведены в табл. 7.4.

Изучение рынка сбыта показало, что суточный спрос на материал В никогда не превышает спроса на материал А более чем на 1 тонну. Кроме того, спрос на материал А никогда не превышает 3 тонн в сутки. Оптовые цены одной тонны материалов равны: 4000 у.е. для В и 3000 у.е. для А. Какое количество материала каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?

Таблица 2.10. Расход продуктов

Исходный продукт	Расход исходных продуктов, т (на одну тонну материалов)		Максимально Возможный запас, т
	Материл А	Материал В
1	3	2	7
2	2	3	9

Решение

1. Формулировка математической задачи:

· переменные для решения задачи: х1- суточный объём производства материала А, х2- суточный объём производства материала В;

· определение функции цели (критерия оптимизации). Суммарная суточная прибыль от производства х1 материала А и х2 материала В равна:

F=4000x2+3000x1

поэтому цель фабрики- среди всех допустимых значений х2 и х1 найти такие, которые максимизируют суммарную прибыль от производства материалов F:

F=4000x2+3000x1-max;

· ограничения на переменные:

- объём производства красок не может быть отрицательным, т.е.

х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. Отчета по результатам Поиска решения

Описание отчетов о решении задачи

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