42053

Математические модели исследования операций. Задача линейного программирования

Лабораторная работа

Информатика, кибернетика и программирование

Цель работы изучить возможности табличного процессора MS Excel для решения задач линейного программирования ЛП. Технология компьютерной реализации прямой задачи ЛП Основным методом решения ЗЛП является симплексметод. Этот метод реализуется с помощью утилиты Поиск решения и решающего блока Solver в табличном процессоре MS Excel. Вызывается командой меню СервисПоиск решения при отсутствии утилиты необходимо вызвать пункт меню Надстройки и в предложенном списке дополнительных модулей выбрать Поиск решения.

Русский

2013-10-27

422.5 KB

9 чел.

Лабораторная работа 1_1. Математические модели исследования операций. Задача линейного программирования.

Цель работы - изучить возможности табличного процессора MS Excel для решения задач линейного программирования (ЛП).

Краткие теоретические сведения

  •  Общая задача ЛП формулируется следующим образом: найти значения неизвестных , доставляющих экстремум (максимум или минимум) линейной целевой функции (ЦФ)

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

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

Решение (план) называется оптимальным, если оно допустимое и доставляет экстремум целевой функции.

  •  Задача ЛП называется канонической, если ограничения задачи состоят из системы уравнений и условий неотрицательности всех n переменных.  

  •  Общая задача ЛП может быть приведена к каноническому виду при помощи следующих утверждений:
  •  неравенство  равносильно равенству  и простейшему неравенству ;

  •  неравенство  равносильно равенству  и простейшему неравенству ;

  •  каждую переменную, на которую не наложено условие неотрицательности,  можно представить в виде разности двух неотрицательных переменных:

  •  вносимые переменные называют дополнительными (вспомогательными); число вводимых дополнительных переменных равно числу неравенств в системе ограничений исходной задачи.

Технология компьютерной реализации прямой задачи ЛП

Основным методом решения ЗЛП является симплекс-метод. Этот метод реализуется с помощью утилиты «Поиск решения» и решающего блока Solver в табличном процессоре MS Excel.  Вызывается командой меню Сервис-Поиск решения (при отсутствии утилиты необходимо вызвать пункт меню «Надстройки» и в предложенном списке дополнительных модулей выбрать «Поиск решения»).

Искомые переменные – ячейки рабочего листа – называются регулируемыми (изменяемыми) ячейками.

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

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

Управление диалоговым окном поиска решения

  •  Установить целевую ячейку – служит для указания целевой ячейки; должна содержать формулу для вычисления ЦФ.
  •  Равной – служит для выбора варианта оптимизации значения целевой ячейки.
  •  Изменяя ячейки – служит для указания ячеек, значения которых изменяются в процессе поиска решения; в этих ячейках должны содержаться переменные оптимизационной модели.
  •  Ограничения – служит для отображения списка граничных условий поставленной задачи.
  •  Выполнить – служит для запуска поиска решения поставленной задачи.
  •  Закрыть – служит для выхода из окна диалога без запуска поиска решения поставленной задачи.
  •  Параметры – служит для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения:
  •  Максимальное время – в поле можно ввести время (в сек.), не превышающее 32767; по умолчанию используется значение 100;
  •  Итерации – служит для управления временем решения путем ограничения числа промежуточных вычислений (по умолчанию 100);
  •  Точность – служит для задания точности вычисления ЦФ;
  •  Допустимое отклонение – служит для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел.
  •  Сходимость – применяется только к нелинейным задачам;
  •  Линейная модель – служит для ускорения поиска решения линейной задачи оптимизации;
  •  Показывать результаты итераций – служит для приостановки поиска решения для просмотра результатов отдельных итераций;
  •  Автоматическое масштабирование – служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине – например, максимизации прибыли в процентах по отношению к вложениям в миллионах рублей.
  •  Значения не отрицательны – позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле Ограничение диалогового окна;
  •  Оценки – служит для указания метода экстраполяции – линейная или квадратичная – используемого для получения исходных оценок значений переменных в каждом одномерном поиске;
  •  Разности – служит для указания метода численного дифференцирования – прямые или центральные производные – используемого для вычисления частных производных целевых и ограничивающих функций. Центральные используются для функций, имеющих разрывную производную;
  •  Метод поиска – служит для выбора алгоритма оптимизации – метод Ньютона или сопряженных градиентов.


  •  Поиск решения позволяет представлять результаты в виде трех отчетов:

Результаты, Устойчивость и Пределы.

Отчет по устойчивости содержит информацию о том, насколько целевая ячейка чувствительна к изменениям ограничений и переменных. Этот отчет имеет два раздела: один для изменяемых ячеек, второй – для ограничений. Раздел для изменяемых ячеек содержит значения нормированного градиента, которое показывает, как целевая ячейка реагирует на увеличение значения  в соответствующей изменяемой ячейке на одну единицу. Подобным образом, множитель Лагранжа в разделе для ограничений показывает, как целевая ячейка реагирует на увеличение соответствующего значения ограничения на одну единицу.

Отчет по результатам содержит три таблицы: в первой приведены сведения о ЦФ до начала вычисления;  во второй – значения искомых переменных, полученные в результате решения задачи; в третьей – результаты оптимального решения для ограничений. Этот отчет содержит также информацию о таких параметрах каждого ограничения, как статус и разница. Статус может принимать три состояния: связанное, несвязанное или невыполненное. Значение разницы – это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения.

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


Пример
. Найти значения переменных, доставляющих максимум ЦФ

Порядок действий.

  1.  Ввести условие задачи

а) создать экранную форму для ввода условия задачи:

  •  переменных;
  •  целевой функции (ЦФ);
  •  ограничений;
  •  граничных условий;

б) ввести исходные данные в экранную форму:

  •  коэффициенты ЦФ;
  •  коэффициенты при переменных в ограничениях;
  •  правые части ограничений;

в) ввести зависимости из математической модели в экранную форму:

  •  формулу для расчета ЦФ;
  •  формулы для расчета значений левых частей ограничений;

г) ввести ограничения и граничные условия (в окне «поиск решения»):

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

2. Решить задачу

а) установить параметры решения задачи условия (в окне «поиск решения»);

б) запустить задачу на решение (условия (в окне «поиск решения»);

в) выбрать формат вывода решения условия (в окне «поиск решения»).

Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными показана на Рис.1.1

     Рис. 1.1

Далее надо ввести зависимости из математической модели (ММ), представляющие собой левые части ограничений и целевую функцию. Данная операция выполняется с помощью функции СУММПРОИЗ, которая позволяет найти скалярное произведение векторов. При вызове функции в первый массив вводятся адреса ячеек, содержащих коэффициенты соответствующего ограничения, а во второй – адреса ячеек с начальными значениями переменных (B10:E10) (см. Рис.1.1). Значения, которые первоначально входят в эти ячейки, обычно нули (незаполненные клетки трактуются по умолчанию как содержащие ненулевые значения).

Замечания. 

  1.  Для проверки правильности введенных формул надо произвести двойное нажатие левой клавиши мыши на ячейки с формулами.
    1.  К моменту вызова сервиса «Поиск решения» на рабочем листе с задачей должны быть занесены формулы для левых частей ограничений  и формула для значения целевой функции.

Технология работы

  1.  Открыть окно Поиск решения (меню Сервис)
  2.  В поле Установить целевую ячейку ввести $F$10 (см. Рис.1.2)
  3.  Из группы Равной выбрать переключатель Максимальное значение
  4.  В поле области Изменяя ячейки ввести ячейки с первоначальными значениями переменных B10:E10.
  5.  Нажав кнопку Добавить, ввести ограничения в соответствии со знаком, принятым в модели. В исследуемой задаче левые части ограничений должны быть меньше или равны правым частям ограничений, и переменные должны быть положительными.

Рис.1.2. Окно «Поиск решения»

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

Рис.1.3. Окно «Параметры поиска решения»

  1.  После нажатия кнопки OK вновь появится диалоговое окно Поиск решения. По нажатии кнопки Выполнить выводится окно Результаты поиска решения (Рис.1.4).

Рис.1.4.

Если решение найдено, следует выделить необходимые типы отчетов, и нажать OK.

  1.  Результат поиска решения исходной задачи

Рис.1.5. Результаты решения задачи (1.1.)

  1.  В отчете по результатам приведены сведения о ЦФ, значениях искомых переменных, и результаты оптимального решения для ограничений.

Рис.1.6. Отчет по результатам задачи (1.1.)

  1.  В отчете по устойчивости дан анализ по переменным о ограничениям

Рис.1.7. Отчет по устойчивости задачи (1.1.)

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

Рис.1.8. Отчет по пределам задачи (1.1.)

  1.  Если решение не найдено, будет выведено соответствующее сообщение.

Рис. 1.9. Сообщение при несовместной системе ограничений задачи

Рис. 1.10. Сообщение при неограниченности ЦФ в требуемом направлении

Иногда сообщения, представленные на рис. 1.9 и 1.10, свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует.

Если при заполнении полей окна "Поиск решения" были допущены ошибки, не позволяющие Excel применить симплекс-метод для решения задачи или довести ее решение до конца, то после запуска задачи на решение на экран будет выдано соответствующее сообщение с указанием причины, по которой решение не найдено. Иногда слишком малое значение параметра "Относительная погрешность" не позволяет найти оптимальное решение. Для исправления этой ситуации надо увеличивать погрешность поразрядно, например от 0,000001 до 0,00001 и т.д.


Контрольные упражнения. Варианты

Решить задачу линейного программирования. Получить отчеты, проанализировать их.

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  

  1.  Построить математические модели следующих  задач и реализовать их в MS Excel

  1.  Для изготовления изделий A, B, C в качестве сырья используется сталь, алюминий и цветные металлы, объемы которых ограничены. Изделия производятся на токарных, фрезерных и шлифовальных станках. Требуется составить план выпуска продукции, при котором будет достигнута максимальная прибыль от ее реализации. Исходные данные приведены в табл. 1

Табл.1

Вид  ресурса

Объем ресурса

Норма расхода на единицу ресурса

A

B

C

Сталь (кг)

800

15

20

40

Алюминий (кг)

600

8

15

10

Цветные металлы (кг)

300

3

6

4

Токарные станки (ч)

4800

60

80

120

Фрезерные станки (ч)

5600

80

70

28

Шлифовальные станки (ч)

600

6

10

12

Прибыль (ден. ед.)

30

40

60

 

  1.  Предприятие для выпуска продукции применяет три технологии и использует 3 вида ресурсов. Известно:

(ед.) – запасы ресурсов;  

(ед./ч) – затраты i-ого вида ресурса на 1 час работы с использованием j-ой технологии;

(руб./ч) – прибыль предприятия от реализации продукции, выпускаемой за 1 ч работы  использованием j-ой технологии;

T (ч) – общее время работы предприятия по всем технологиям.

Требуется найти время работы предприятия, необходимое по каждой технологии, для обеспечения максимальной прибыли от реализации выпускаемой продукции. Составить математическую модель задачи при T=300 ч. по исходным данным, приведенным в табл.2.

    

   Табл.2

Вид  ресурса

Запасы ресурса

Затраты работы за 1 ч работы по технологии

№1

№2

№3

1

800

8

5

10

2

1800

12

10

9

3

1100

12

11

5

Прибыль  

600

800

750