Методическая разработка по теме "Линейное программирование в МДК 3.2 специальности 09.02.03"

МДК 3.2 Инструментальные средства разработки программного обеспечения

• Раздел 8. Линейное программирование

Понятия о моделях и моделировании.

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

Модель частично или полностью воспроизводит структуру моделируемой системы, её функции.

Моделирование

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

Элементы моделирования

• Субъект – человек-исследователь;
• Объект исследования;
• Модель объекта , как связующее звено между субъектом и объектом

Цели моделирования

• Хорошо построенная модель доступнее, информативнее и удобнее для исследователя, нежели реальный объект.
• Модель позволяет научиться правильно управлять объектом путем апробирования различных вариантов управления.

Модель нужна для того, чтобы:

• (1) понять, как устроен конкретный объект: какова его структура, внутренние связи, основные свойства, законы развития, саморазвития и взаимодействия с окружающей средой;

Модель нужна для того, чтобы:

( 2) научиться управлять объектом или процессом, определять наилучшие способы управления при заданных целях и критериях;

Модель нужна для того, чтобы:

( 3) прогнозировать прямые и косвенные последствия реализации заданных способов и форм воздействия на объект.

Этапы процесса моделирования

• Постановка проблемы, выработка цели исследования;
• Переход от оригинала к модели, т.е. построение модели;
• Экспериментальное исследование модели;
• Перенесение результатов исследования на оригинал.

:   Виды моделей:  

· физические;   · аналоговые ;   · математические.

Физическая модель

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

Аналоговая модель

представляет собой исследуемый объект аналогом, который ведет себя как реальный объект, но не выглядит как таковой

Математические модели

характеризуют реальную систему символическими уравнениями или неравенствами.

  Универсальность математического языка делает математические модели наиболее удобным инструментом изучения объекта, его основных свойств.

Математическая модель

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

Математическая модель

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

Суть математического моделирования

состоит в выборе, обосновании и построении (синтезе и анализе) математических моделей.

МАтематическое моделирование =

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Задача программирования утреннего одевания

• Носки
• Ботинки
• Брюки
• Пиджак
• Рубашка
• Галстук

Гардероб:

Цель – затратить на процедуру одевания минимум времени.

Количество вариантов

одевания = 6! = 720

Ограничения: Всё множество вариантов одевания можно условно разбить на 2 подмножества: допустимые и недопустимые.

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

Задачи линейного программирования (ЗЛП)

- образуют подмножество задач математического программирования.

Отличительная особенность ЗЛП:

• Цель записывается с помощью линейной функции,
• Ограничения – линейны.

Вычисление экстремума (максимума или минимума) линейной функции при условии, что переменные, подлежащие определению, удовлетворяют линейным ограничениям, составляют

Предмет линейного программирования.

Некоторые даты

Конец 30-х годов ХХ века – основы линейного программирования описаны советским математиком Л. В. Канторовичем;

1941-в США построена модель транспортной задачи;

1947 – создание симплекс-метода Дж. Данцигом;

1949 – метод потенциалов (Л.В. Канторович и М.К. Гавурин);

Этапы построения оптимизационных экономико-математических моделей

• 1 этап – выбор объекта исследования

• 2 этап – определение цели исследования

• 3 этап – выбор критерия оптимальности

• 4 этап – выявление основных ограничений

Задача об использовании ресурсов

Требуется составить такой план выпуска продукции, чтобы при её реализации получить максимальный доход.

Задача о смесях

• Для откорма животных необходимо из двух кормов К1 и К2 составить смесь.
• Задана питательная ценность порции смеси на одного животного, т.е. в ней должно содержаться: белков – не менее 12 ед., жиров – не менее 6 ед., углеводов – не менее 9 ед.

Задача о смесях (продолжение)

• Требуется смешать имеющиеся корма в таком количестве, чтобы обеспечить заданную питательность смеси при минимальных затратах на корма.

Общая задача линейного программирования

Основные определения

• Линейная функция f называется целевой функцией задачи.

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

Основные определения

• Любая совокупность x  0 (j =1,…n),

удовлетворяющая ограничениям, называется допустимым решением задачи.

• Если ЗЛП имеет хотя бы одно допустимое решение, то её ограничения называют совместными , в противном случае – несовместными .

Основные определения

• Все допустимые решения образуют область определения ЗЛП, или область допустимых решений.
• Допустимое решение, максимизирующее или минимизирующее целевую функцию f, называется оптимальным решением задачи.

Каноническая (основная) форма задачи линейного программирования

Задача линейного программирования записана в канонической форме если:

• Целевая функция максимизируется;

• Ограничения имеют вид равенств с неотрицательной правой частью;

• Все переменные неотрицательны.

Задача линейного программирования в канонической форме имеет вид:

Частный вид ЗЛП (1)

Для того, чтобы левая часть ограничения была равна правой

необходимо к левой части каждого ограничения прибавить соответственно неотрицательные переменные х n+1 , х n+2 ,…, х n+m .

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

После приведения к канонической форме ЗЛП (1) будет иметь вид:

Дополнительные переменные

Переменные х n+1 , х n+2 ,…, х n+m называются дополнительными.

Для задачи использования ресурсов с аналогичной моделью дополнительные переменные интерпретируются как количество неиспользуемых ресурсов.

Частный вид ЗЛП (2)

Определение минимального значения целевой функции f можно свести к определению максимального значения функции (-f), так как min f = -max(-f).

Для приведения ограничения вида «≥» к ограничениям-равенствам необходимо из левой части каждого ограничения вычесть соответственно неотрицательные переменные х n+1 , х n+2 ,…, х n+m .

Эти переменные вводятся в целевую функцию

с нулевыми коэффициентами, чтобы не изменить

её значение.

После приведения к канонической форме ЗЛП (2) будет иметь вид:

Экономический смысл дополнительных переменных

Полученная модель аналогична модели задачи о смесях (о диете), поэтому для этой задачи дополнительные переменные будут экономически интерпретироваться как количество питательных веществ в смеси сверх заданного нижнего предела.

Базисные решения ЗЛП

• Для решения ЗЛП симплекс-методом необходимо привести её к канонической форме и определить исходное базисное решение.
• Определить базисное решение можно путём последовательных элементарных преобразований ограничений.

Совместная система и ранг матрицы

• Система, имеющая хотя бы одно решение, называется  совместной ; система, не имеющая ни одного решения —  несовместной .
• Рангом   матрицы  А  с  m  строк и    n столбцов называется максимальное число  линейно независимых  строк.
• Несколько строк называются линейно независимыми, если ни одна из них не выражается линейно через другие.

Ограничения в ЗЛП в канонической форме

• Ограничения в ЗЛП в канонической форме представляют собой систему m линейных уравнений с n переменными.

• Будем считать, что m Система совместна, и ранг её матрицы равен m .

В ограничениях задачи все переменные можно разделить на 2 группы:

• Основные (зависимые) переменные, число которых равно числу линейно-независимых уравнений m.
• Неосновные (независимые) переменные, число которых будет равно n-m.

После некоторых элементарных преобразований ограничения ЗЛП в канонической форме могут быть приведены к виду:

В полученной системе коэффициенты при каждом неизвестном x 1 , x 2 , …x m образуют единичные векторы:

Определения (1)

Совокупность единичных векторов Е 1, Е 2,…, Е т образует базис m-мерного пространства, а переменные х 1 , х 2 ,…, х m называются базисными.

Переменная является базисной , если она входит только в одно из уравнений системы с коэффициентом равным 1.

Определения (2)

Частное решение, полученное путём приравнивания небазисных переменных нулю и нахождения значений базисных переменных, называется базисным решением .

Следовательно, если х m+1 =0, х m+2 =0,…,

х n =0, то х 1 =b ’ 1 , х 2 = b ’ 2 ,…, х m = b ’ m

Определения (3)

• Базисное решение называется вырожденным , если значения одной или нескольких базисных переменных равны нулю.
• Задача, имеющая хотя бы одно вырожденное базисное решение , называется вырожденной , в противном случае – невырожденной .

Спасибо за внимание!