Линейное программирование. Сущность линейного программирования

Бюджетное профессиональное образовательное учреждение

Омской области «Сибирский профессиональный колледж»

МАТЕМАТИЧЕСКИЕ МЕТОДЫ. Линейное программирование.

Пособие

Для студентов очной формы обучения специальности

Программирование в компьютерных системах»

Омск 2015

Содержание

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА.. 3

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.. 4

Практические работы... 9

Практическая работа № 1. «Построение математической модели задачи линейного программирования» 9

Практическая работа №2. «Графическое решение задачи линейного программирования». 12

Практическая работа №3. «Симплексный метод решения задачи линейного программирования» 18

Практическая работа № 4. «Симплексные таблицы». 22

Практическая работа № 5. «Расчет задач линейного программирования с использованием MS Excel» 26

Практическая работа № 6.1. «Транспортная задача. Метод Северо-западного угла». 31

Практическая работа №6.2. «Транспортная задача. Метод наименьших затрат». 35

Практическая работа № 7. «Транспортная задача. Открытая модель». 37

Практическая работа № 8.1. «Транспортная задача. Проверка оптимальности решения. Метод потенциалов». 40

Практическая работа № 8.2. «Транспортная задача с ограничениями». 45

Практическая работа № 8.3. «Решение транспортной задачи с помощью MS Excel». 48

Практическая работа № 9. «Задача о назначениях». 51

Практическая работа № 10. «Решение задачи о назначениях с помощью MS Excel». 55

Индивидуальная контрольная работа.. 57

ЗАКЛЮЧЕНИЕ.. 62

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 63

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Настоящее учебное пособие разработано для студентов очной формы обучения специальности 230115 «Программирование в компьютерных системах» при изучении дисциплины «Математические методы».

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

ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование. Сущность линейного программирования

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

Исследование операций – это наука, занимающаяся разработкой и практическим применением методов наиболее эффективного (оптимального) управления организационными системами.

Целью исследования операций является количественное обоснование принимаемых решений для выявления лучшего (оптимального) способа действий при решении той или иной задачи организационного управления.

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

При решении конкретной задачи управления применение методов исследования операций предполагает:

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

2. Изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия.

Основные этапы исследования операций:

1. Постановка задачи;

2. Построение экономико-математической модели;

3. Определение метода решения задачи;

4. Решение задачи;

5. Проверка и корректировка математической модели;

6. Реализация найденного решения на практике.

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

Задача 1. Для обеспечения высокого качества выпускаемых изделий на заводе организуется система выборочного контроля. Требуется выбрать такие формы его организации — например, назначить размеры контрольных партий, указать последовательность контрольных операций, определить правила отбраковки, — чтобы обеспечить необходимое качество при минимальных расходах.

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

Задача 3. К заданному сроку необходимо провести массовое медицинское обследование группы населения с целью выявления определенных заболеваний. На обследование выделены материальные средства, оборудование, персонал. Требуется разработать такой план обследования — установить число медпунктов, их размещение, вид и количество анализов, чтобы выявить как можно больший процент из числа заболевших.

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

Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель. В задаче 1 — это организация выборочного контроля с целью обеспечить качество выпускаемой продукции; в задаче 2 — организация временных торговых точек с целью проведения сезонной распродажи; в задаче 3 — массовое медицинское обследование с целью определения процента заболевших. В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение — такое, чтобы мероприятие принесло определенную выгоду. Условиями проведения операции в каждой задаче оказываются средства, которыми мы располагаем, время, оборудование, технологии, а решение в задаче 1 заключается в выборе формы контроля — размера контрольных партий, правил отбраковки; в задаче 2 — в выборе числа точек размещения, количества персонала; в задаче 3 — в выборе числа медпунктов, вида и количества анализов.

Рассмотрим краткое содержание каждого этапа исследования операций.

1 этап. Постановка задачи.

Постановка задачи – это чрезвычайно ответственный этап операционного исследования.

Первоначально задачу формулируют с точки зрения заказчика. Такая постановка задачи обычно не бывает окончательной. Во время анализа исследуемой системы задача постепенно уточняется.

2 этап. Построение экономико-математической модели.

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

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

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

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

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

Все факторы, входящие в описание операции, можно разделить на две группы:

1. Постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через α₁,α₂,……;

2. Зависимые факторы (элементы решения) x1,x2,…. которые в известных пределах мы можем выбирать по своему усмотрению.

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

Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде

Z=f(x₁, x₂, …., α₁, α_2,….)

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

(1)

и обращающие в максимум(или минимум) целевую функцию, т.е.

(2)

(Условия неотрицательности переменных, если они есть, входят в ограничения (1))

Как известно, упорядоченная совокупность значений n переменных x₁, x₂,….. x_n представляется точкой n-мерного пространства. В дальнейшем эту точку будем обозначать Х= (x₁, x₂,….. x_n), а само оптимальное решение Х*= (x₁*, x₂*,….. x_n*).

Таким образом, математическая модель задачи линейного программирования (ЗЛП) составляется путем экономического анализа по следующей схеме:

1. Вводят переменные;

2. Формируют целевую функцию;

3. Формируют ограничения;

4. Налагают условия неотрицательности переменных (или указывают интервалы изменения переменных).

3 этап. Определение метода решения задач.

Для нахождения оптимального решения Х* в зависимости от структуры математической модели и существующих ограничений применяются следующие методы математического программирования:

1. Линейное программирование применяют в том случае, когда функции ¦и φ являются линейными функциями относительно переменных;

2. Нелинейное программирование, если ¦ и φ – нелинейные функции;

3. Динамическое программирование применяется в том случае, когда ¦ и φ имеет специфическую структуру и их поведение на каждом этапе зависит от всех предыдущих состояний;

4. Стохастическое программирование применяют в том случае, когда переменные x и y являются случайными величинами;

5. Дискретное программирование применяется в том случае, если на переменные x и y наложено условие дискретности (они могут принимать значение только 0 и 1);

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

4 этап. Решение задач.

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

5 этап. Проверка и корректировка математической модели.

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

6 этап. Реализация решения на практике.

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

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

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

– показатель эффективности (целевая функция) зависит линейно от элементов решения x₁, x₂,...,x_n;

– ограничения, наложенные на элементы решения, имеют вид линейных равенств или неравенств относительно x₁, x₂,...,x_n.

Такие задачи довольно часто встречаются на практике, например, при решении проблем, связанных с распределением ресурсов, планирования производства, организацией работы транспорта и т. д. Это естественно, т. к. во многих задачах практики «расходы» и «доходы» линейно зависят от количества закупаемых средств.

В линейном программировании используются две основные аксиомы:

1. Аддитивности, т.е. полное количество ресурсов, затрачиваемых на производство единицы продукции равно сумме всех ресурсов;

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

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основой задачей линейного программирования», которая формулируется так:

Дана система m линейных уравнений и неравенств с n переменными

(3)

и линейная функция .

Необходимо найти такое решение системы , где

при котором линейная функция F принимает оптимальное (то есть максимальное или минимальное) значение.

Система (3) называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функцией или функцией цели.

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

Операция – система действий, объединенная единым замыслом и направленная к достижению поставленной цели.

По содержательной постановке можно выделить следующие типичные классы задач:

1. Задачи управления запасами.

2. Задачи распределения ресурсов.

3. Задачи ремонта и замены оборудования.

4. Задачи массового обслуживания.

5. Задачи упорядочения.

6. Задачи сетевого планирования и управления.

7. Задачи выбора маршрута и другие.

Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы — детерминированными, динамические процессы — статическими моделями и т.д. Жизнь богаче любой схемы.

Практические работы