Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

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

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

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

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

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

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

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

Фирма выпускает два типа строительных материалов: А и В. продукция обоих видов поступает в продажу. Для производства материалов используются два исходных продукта: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+3000x1max;

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

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

х2 0, х1 0;

• расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т.е.:

2х2+3х1 7,

3х2+2х1 9,

• ограничения на величину спроса на материалы:

х1-х2 1,

х1 3,

• Найти максимум следующей функции:

F=4000x2+3000x1max,

• При ограничениях вида:

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

1. Математическая постановка двойственной задачи о красках

Напомним, что исходная постановка задачи о красках сформулирована в форме (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).

Характеристики

Список файлов ВКР