Задача оптимального планирования реферат

Обновлено: 03.07.2024

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

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

Математические знания необходимы и будущим биологам, и филологам, экономистам и юристам, агрономам и инженерам.

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

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

2.1. Пояснительная записка

Моделирование процессов оптимального планирования (19 ч)

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

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

Критерием оптимальности могут быть различные параметры; например, в экономике можно стремиться к максимальному количеству выпускаемой продукции или к ее низкой себестоимости. Оптимальное развитие соответствует экстремальному (максимальному или минимальному) значению выбранного целевого параметра.

Использование компьютера для исследования информационных моделей различных объектов и систем позволяет изучить их в зависимости от значения тех или иных параметров. Процесс разработки моделей и их исследование на компьютере можно разделить на несколько этапов:

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

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

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

1. Познакомить студентов с методами математического исследования.

2. Сформировать умения и навыки:

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

формированию мотивации;
развитию логического мышления, самообразования

■ Этапов математического моделирования

■ Основной задачи линейного программирования и методов ее решения

■ Реализовать этапы построения моделей при решении производственных задач

■ Решать задачи линейного программирования различными способами (графическим, симплексным), с использованием программных средств.

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

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

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

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

Постановка задач оптимального планирования. Линейное программирование — введение.

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

Графический метод решения задач линейного программирования.

Графо-аналитический метод решения задач линейного программирования с помощью Ms Excel.

Решение задач оптимизации с помощью пакета MathCAD.

Алгоритмическая реализация симплекс-метода.

Программная реализация симплекс-метода в VBA; сопоставление с Turbo-Pascal.

Блок практических заданий.

Тема 1 . Постановка задач оптимального планирования. Линейное программирование — введение.

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

Тема 2 : Определение линейного программирования. Существование и единственность решения.

Тема 3 . Графический метод решения задач.

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

Тема 4 : Использование электронных таблиц при решении задач линейного программирования графическим способом.

Использование программных средств при решении задач

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

Тема 6 . Возможности математического пакета MathCAD для решения задач линейного программирования.

Тема 7 . Симплекс-метод.

Идея симплексного метода как метода последовательного улучшения. Понятие базисного решения. Фундаментальная теорема линейного программирования. Симплексная таблица. Отыскивание начального базиса, понятие искусственного базиса.

Тема 8 . Алгоритм решения задач симплексным методом.

Тема 9 . Использование языков программирования (Visual Basic, Turbo Pascal) для реализации симплекс-метода.

2. 2. Разработки занятий

Тема : Постановка задач оптимального планирования. Линейное программирование: введение.

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

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

Постановка задачи планирования выглядит следующим образом:

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

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

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

Приведем несколько примеров.

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

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

Пусть станция технического обслуживания автомобилей выполняет два вида обслуживания: ТО-1 и ТО-2. Автомобили принимаются в начале рабочего дня и выдаются клиенту в конце дня. В силу ограниченности площади стоянки за день можно обслужить в совокупности не более 140 автомобилей. Рабочий день длится 8 часов. Если бы все автомобили проходили только ТО-1, то мощности станции позволили бы обслужить 200 автомобилей в день, если бы все автомобили проходили только ТО-2, то 50 автомобилей в день. Стоимость (для клиента) ТО-2 вдвое выше, чем ТО-1. Реально за день часть автомобилей проходит ТО-1, а часть – ТО-2. Требуется составить такой дневной план обслуживания, чтобы обеспечить предприятию наибольшие денежные поступления.

Построим математическую формулировку задачи. Плановыми показателями являются:

х - дневной план выполнения ТО-1;

у - дневной план выполнения ТО-1.

Из условий задачи ресурсами являются:

длительность рабочего дня – 8 часов;
вместимость стоянки – 140 мест.

Из постановки задачи следует, что на ТО-2 затрачивается в 4 раза больше времени, чем на ТО-1. Если обозначить продолжительность ТО-1 как t минут, то продолжительность ТО-2 составит 4 t минут. Отсюда следует, что суммарное время на выполнение x обслуживаний ТО-1 и y обслуживаний ТО-2 равно:

tx + 4 ty = ( x + 4 y ) t .

Но это время не может быть больше длительности рабочего дня. Отсюда следует:

Подсчитаем время t для выполнения ТО-1. Поскольку за рабочий день обслуживаний вида ТО-1 может быть выполнено 200, то на одно ТО-1 тратится 480/200 = 2,4 (минут). Подставляя значение в неравенство, получим:

Полученное значение 2,4 минуты является не физическим временем выполнения одного ТО-1, поскольку оно требует гораздо большего времени, а среднем временем для данной станции, имеющей несколько боксов.

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

К двум полученным неравенствам следует добавить условия положительности значений величин x и y (число автомобилей не может быть отрицательным). В конечном итоге получим систему неравенств:

А теперь перейдем к формализации стратегической цели: получить максимальные денежные поступления. Пусть стоимость выполнения одного ТО-1 составляет r рублей. По условиям задачи стоимость выполнения одного ТО-2 в два раза больше, т.е. 2 r рублей. Отсюда полная выручка предприятия за день равна

rx + 2 ry = r ( x +2 y ).

Поскольку r – константа, то максимальное значение полной выручки будет достигнуто при максимальном значении

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

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

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

Тема: Общая формулировка и существование решения задач линейного программирования.

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

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

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

Запишем это определение с помощью формул. Дана система линейных уравнений и неравенств:

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

Требуется найти такое неотрицательное решение

системы, чтобы функция f принимала наименьшее (или наибольшее) значение.

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

Рассмотрим на примере задачи с двумя переменными, как может сложиться ситуация с разрешимостью задач линейного программирования. Пусть переменные x, y удовлетворяют m ограничениям-неравенствам

и стандартным ограничениям

Требуется отыскать экстремум линейной функции f = ax+by .

Каждое из неравенств на координатной плоскости выделяет полуплоскость; то же делают стандартные ограничения.

Возможны лишь три разных случая расположения этих полуплоскостей:

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

Рис. 1 Иллюстрация к различным ситуациям системы ограничений

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

На рис.1, б пересечение полуплоскостей образуют многоугольник. Будем перебирать значения f в уравнении f = ax+by и получим семейство параллельных прямых, одна из которых будет соответствовать наибольшему, а другая - наименьшему значению f с учетом наличия ограничений. В этом случае могут быть две разные ситуации (рис.2, а,б ).

Рис. 2 Иллюстрации к единственности и множественности решений.

Пунктирные линии на рис.2 – семейство прямых f = ax+by , при возрастании значения f прямые смещаются вправо: искомая прямая соприкасается с многоугольником лишь с одной вершиной или вдоль стороны. В случае, показанном на рис.2, а , задача имеет единственное решение, соответствующей точке касания пунктирной прямой многогранника в его вершине, в случае на рис.2, б – бесконечное множество решений: координаты любой из точек линий соприкосновения, если пунктирная прямая оказалась параллельной стороне многогранника.

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

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

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

Тема : Графический метод решения задач линейного программирования.

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

Неравенство определяет граничную прямую , которая делит плоскость на две полуплоскости: положительную и отрицательную .

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

Необходимо определить полуплоскость для неравенства . На плоскости координат строим граничную прямую, определяемую равенством , по двум точкам А (0; 3) и В (2; 0). Граничная прямая не проходит через начало координат, поэтому подставляем координаты точки О (0; 0) в неравенство. Получаем верное неравенство 3*0+2*0 . Полуплоскость, удовлетворяющую неравенству, будем отмечать штриховкой.

Область допустимых решений.

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

Требуется определить область допустимых решений в задаче:

Совхоз для производства двух видов продукции использует четыре вида производственных ресурсов.

Введение¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬¬.
1. Характеристика направлений перевозок и флота.
2. Подготовка исходных данных и составление математической модели задачи.2.1 Построение возможных вариантов схем движения судов.
2.2 Расчет нормативов работы судов на схемах движения.
2.3 Составление математической модели задачи.
3. Нахождение оптимального плана работы флота и оптимальных схем движения судов.
4.Расчет основных плановых показателей работы флота.
Заключение.
Список литературы.

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

1.ХАРАКТЕРИСТИКА ФЛОТА И НАПРАВЛЕНИЙ ПЕРЕВОЗОК

Характеристики Ед. измерения Коммунист Андижан
Длина максимальная м 154,6 104,2
Ширина м 20,6 14,4
Высота борта м 12,7 7,9
Осадка максимальная м 9,0 6,6
Дедвейт т 12700 4388
Чистая грузоподъёмность т 11040 4063
Грузовместимость
-кип м3 17860 5635
-насыпью м3 19520 5916
Скорость:-в грузу узл. 16,5 13,0
-в балласте узл. 17,5 14,2
Дальность плавания мили 14000 6000
Ледовой класс Л2 Л2
Расход топлива в сут. -на ходу т/сут 38,4 9,3
-на стоянке т/сут 2,7 0,5
Численность экипажа чел. 37 32
Затраты на содержание судна в эксплуатации,
-на ходу грн./сут 4416 1797
-на стоянке грн./сут 3048 1429Характеристики портов
К перевозке предъявлены грузы на следующих участках: Ильичёвск – Салоники (1), Салоники – Стамбул (2), Стамбул – Ильичёвск (3), Салоники – Ильичёвск (4), а также балластные участки Стамбул – Салоники (5), Ильичёвск – Салоники (6).
Таким образом наши суда будут заходить в порты Ильичёвск (Украина), Салоники (Греция), Стамбул (Турция).

Ильичевск, Украина (Ilyichevsk)Ильичевский морской торговый порт – один из крупнейших портов Украины, основан в 1958 г. На базе грортом узового района Одесского порта. Одновременно с новым портом развивился и город-спутник – Ильичевск, который приобрел статус города в 1973 г. Сегодня это современный город с хорошо развитой инфаструктурой, промышленностью. Здесь, в частности, расположен один из крупнейших.

Графический метод решения задач оптимального планирования ( реферат , курсовая , диплом , контрольная )

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

Цель: реализовать на ЭВМ алгоритм решения системы линейных уравнений размерностью MN, представленных в матричном виде. Рассмотреть случаи: M N с точки зрения существования и единственности решения.

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

Переменные величины, действуя на которые можно достигнуть поставленной цели, называют планом, или вектором управления X=(x1, x2, …, xn). Для достижения цели имеются некоторые материальные, финансовые, трудовые и другие ресурсы, технологии и способы производства. Обозначим вектор этих ресурсов через A=(b1, b2, …, bm). Цель операции формализуется в виде критерия оптимальности и системы ограничений.

Обозначим критерий оптимальности (целевую функцию) через

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

Таким образом, общая детерминированная модель математического программирования примет вид:

max (min): Z = z (X), X.

Допустимый план X, доставляющий критерию оптимальности Z = z (X) экстремальное значение, называется оптимальным и обозначается через X*, экстремальное значение целевой функции — через Z* = z (X*).

Задача оптимального использования ресурсов Имеется M видов ресурсов, заданных вектором A0=(b1, b2, …, bm). Задана матрица A=|| aij ||, где aij — норма расхода I-го ресурса на единицу j-той продукции (I=1,…, m; j=1,…, n). Эффективность выпуска единицы j-той продукции характеризуется, например, прибылью pj. Требуется определить план выпуска продукции X=(x1, x2, …, xn), обеспечивающий максимальную прибыль предприятия при заданных ресурсах, т. е.

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

Пример. Предприятие может изготовлять 4 вида продукции П-1, П-2, П-3, П-4. Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 человеко — смен, полуфабрикатами массой 260 кг, станочным оборудованием в 370 станко — смен. Нормы расхода ресурсов и прибыль от единицы каждого вида продукции представлены в таблице:

Трудовые ресурсы, чел — смен

Станочное оборудование, станко — смен

Прибыль от ед-цы продукции

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

Целевая функция — максимум прибыли:

max: Z = 40×1 + 50×2 + 100×3 + 80 x4

на трудовые ресурсы:

2,5×1 + 2,5×2 + 2×3 + 1,5×4 100

4 x1 + 10×2 + 4×3 + 6×4 260

на станочное оборудование:

8 x1 + 7×2 + 4×3 + 10×4 370

Решение систем линейных уравнений.

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

Если система линейных уравнений независимая (т.е. никакое уравнение нельзя выразить линейно через другие), то решением системы будет :

а) точка пересечения плоскостей пространства (или точка пересечения прямых в случае двух переменных) X=(x1, x2, …, xn) — единственное решение (случай M=N);

б) прямая пресечения плоскостей — множество решений (случай M>N);

в) нет решений (случай M

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

Итак, для решения задачи оптимального управления оптимален случай а), когда возможно единственное решение — X=(x1, x2, …, xn). Используя введенные ранее обозначения и принимая по определению M=N, система ограничений примет вид:

a11×1 + a12×2 + … + a1n xn = b1

a21×1 + a22×2 + … + a2n xn = b2

an1 x1 + an2 x2 + … + ann xn = bn

Существует множество стандартных способов решения системы линейных уравнений. Рассмотрим один из наиболее удобных способов, основанный на матричном методе решения. Анализируя внешний вид матрицы и системы, можно сделать вывод — чтобы получить решение X=(x1, x2, …, xn) достаточно, например, получить коэффициенты, равные 1 перед диагональными неизвестными, и 0 — перед остальными неизвестными. Тогда результаты последнего столбца и будут решением системы. По правилам работы с матрицами, разрешается выполнять со строками следующие действия:

а) умножение (деление) коэффициентов строки на одно и тоже число;

б) сложение (вычитание) коэффициентов строк;

в) перемена строк местами.

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

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

1x1 + 0×2 + … + 0 xn = 1 или x1=1

0 x1 + 1×2 + … +0 xn = 2×2=2

0 x1 + 0×2 + … + 1 xn = n xn=n

Так как по условию задачи план является вектором управления X=(x1, x2, …, xn), то решением задачи можно считать последний столбец расширенной конечной матрицы (такую матрицу называют единичной).

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

1шаг. Чтобы получить 1 на главной диагонали 1-й строки, поменяем местами 1-ю и 3-ю строки

2шаг. Получим 0 под диагональным коэффициентом 1-й строки во 2-й и 3-й строках. Для этого умножим 1-ю строку на 4 и вычтем из 2-й строки, а затем умножим 1-ю строку на 5 и вычтем из 3-й строки.

3 шаг. Чтобы получить 1 на главной диагонали 2-й строки, разделим коэффициенты 2-й строки на 2.

4 шаг. Получим 0 под диагональным коэффициентом 2-й строки в 3-й строке. Для этого умножим коэффициенты 2-й строки на 4 и вычтем из 3-й строки.

5 шаг. Чтобы получить 1 на главной диагонали 3-й строки, разделим коэффициенты 3-й строки на 9.

6 шаг. Чтобы получить 0 во 2-й строке над диагональным коэффициентом 3-й строки, сложим коэффициенты 3-й и 2-й строки.

7 шаг. Чтобы получить 0 в 1-й строке над диагональным коэффициентом 2-й строки, вычтем из 1-й строки коэффициенты 3-й строки.

Результатом задачи является последний столбец матрицы. Действительно, если произвести проверку, решение (2, 1, 0) является верным для каждой строки матрицы.

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

Т.о. приведение матрицы к диагональному виду можно свести к двум общим правилам:

получить 1 на главной диагонали матрицы и 0 под главной диагональю, начиная с первой строки;

получить 0 во всех строках над главной диагональю, начиная преобразования с последней строки.

Задание Реализовать на ЭВМ алгоритм решения системы линейных уравнений, применяя матричный способ (см. пример).

Замечания. 1) Рекомендуется производить вывод всех промежуточных матриц на экран.

Учесть случай, когда после преобразования на главной диагонали получается 0.

После окончания преобразования произвести проверку результата и вывести на экран.

литература

Балашевич В. А. Основы математического программирования.

Вентцель Е. С. Исследование операций.

лабораторная работа № 2

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

Напомним, что задача линейного программирования сводится к нахождению некоторой совокупности переменных xj, j=1, 2, …, n, доставляющих линейной функции цели экстремальное значение и удовлетворяющих системе ограничений в форме равенств или неравенств, т. е. необходимо найти план

который придает экстремальное значение линейной функции

max (min): Z = z (X), (1)

при системе ограничений:

Линейная функция (1) называется целевой, множество планов X, удовлетворяющих системе ограничений (2) — (5) — множеством допустимых решений и обозначается, X.

Допустимый план X, доставляющий целевой функции (1) экстремальное значение, называют оптимальным X*.

Задача (1) — (5) включает общую постановку задачи линейного программирования.

Основная теорема линейного программирования.

Следующая теорема позволяет выбрать единственное решение задачи при наличии множества допустимых решений:

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

Базисные и опорные планы.

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

Базисные планы с неотрицательными компонентами — опорные.

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

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

Пусть. Зафиксируем Z. Тогда целевая функция будет представлять гиперплоскость, во всех точках которой значение Z не меняется. При изменении Z получим семейство гиперплоскостей уровня цели. Так как при изменении Z коэффициенты cj не меняются, то семейство гиперплоскостей уровня цели есть множество параллельных гиперплоскостей. При этом вектор C=(c1, c2, …, cn) называют вектором максимального возрастания целевой функции или градиентным направлением. При перемещении некоторой фиксированной гиперплоскости уровня цели в градиентном направлении C=(c1, c2, …, cn) значение Z возрастает скорейшим образом.

В случае двух переменных при изменении Z получаем семейство параллельных прямых — линии уровня цели: c1+c2 .

Геометрическое решение задачи в случае двух переменных.

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

max (min): Z=c1x1+c2x2;

ai1x1+ai2x2 R bi, i=1, …, m; x1 0, x2 0,

то ее графически можно решить в следующей последовательности:

Построить множество допустимых решений, с учетом системы ограничений.

Построить вектор градиентного направления C=(c1, c2, …, cn).

Построить произвольную линию уровня цели Z=const (например, Z=0), перпендикулярно к вектору C=(c1, c2, …, cn).

При решении на max переместить прямую Z=const в направлении вектора C=(c1, c2, …, cn) так, чтобы она заняла крайнее положение.

В случае на min линию уровня цели Z=const переместить в антиградиентном направлении.

Определить оптимальный план. Возможны следующие случаи:

а) оптимальный план единственный. Тогда линия уровня цели Z и область в крайнем положении будут иметь одну общую точку.

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

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

г) Задача решения не имеет. Область допустимых решений — пустое множество, т. е. система не совместна.

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

Модель задачи имеет вид:

Исходя из графического решения задачи, оптимальный план соответствует угловой точке многоугольника с координатами X=(4; 3). Значение целевой функции в данной точке составляет Z=11. Проверка: по теореме линейного программирования наилучшие решения задачи представляют собой угловые точки многоугольника решений. Таким образом, достаточно проверить значение целевой функции в каждой угловой точке и выбрать максимальное:

Итак, оптимальное решение X*= (4; 3) и Z (X*) = 11.

Задание Реализовать на ЭВМ алгоритм решения задачи определения оптимального плана выпуска 2-х видов продукции X=(x1, x2). Объемы ресурсов предприятия представлены вектором A=(b1, b2, …, bm), прибыль (затраты) на единицу продукции представлены вектором C=(c1, c2), а нормы затрат ресурсов на единицу продукции представлены матрицей || aij ||, i=1,…, m; j=1,2. Определить оптимальный план выпуска 2-х видов продукции, используя графический метод решения задачи с 2-мя переменными.

Замечание. Критерий оптимальности задачи должен быть задан с клавиатуры, т. е. задача должна определять максимум или минимум целевой функции по выбору пользователя.

литература

Балашевич В. А. Основы математического программирования.

Вентцель Е. С. Исследование операций.

лабораторная работа № 3

Цель: научиться задавать систему ограничений в предпочтительном виде и строить начальную симплекс-таблицу; реализовать на ЭВМ симплекс-метод построения оптимального плана управления с помощью улучшения симплекс-таблицы; провести анализ и определить случаи невозможности улучшения плана.

Построение начального опорного плана.

Рассмотрим задачу линейного программирования с системой ограничений, представленных в каноническом виде:

Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая содержит переменную, входящую с коэффициентом 1, а остальные ограничения — равенства с коэффициентом 0.

Пример. В системе ограничений

x1 + 2×2 — 4×4 = 5 — предпочтительный вид

— 2×2 + x3 + 2×4 = 8 — предпочтительный вид

x2 — 3×4 = 3 — нет Если каждое ограничение системы ограничений — равенств имеет предпочтительный вид, то и система представлена в предпочтительном виде. В этом случае легко найти ее опорное (базисное) решение. Все переменные, кроме предпочтительных, нужно приравнять к нулю. Тогда предпочтительные переменные примут значения, равные правым частям. Полученный план будет опорным (базисным).

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

1 случай. Пусть Добавим к левым частям дополнительные переменные xn+i 0, i = 1, …, m и получим расширенную задачу. В расширенной задаче система ограничений имеет предпочтительный вид:

Следовательно, начальный опорный план преобразуется в вектор X0 = (0, …, 0, b1, b2, …, bm). В целевую функцию дополнительные переменные вводятся с коэффициентом 0.

2 случай. Пусть Вычтем из левых частей дополнительные переменные xn+i 0, i = 1, …, m и получим расширенную задачу, эквивалентную исходной. Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть с коэффициентами -1. Поэтому план X0 = (0, …, 0, b1, b2, …, bm) недопустим. В этом случае вводят так называемый искусственный базис:

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

Полученная задача называется М — задачей, соответствующей исходной:

Если ни одно из ограничений не имеет предпочтительный вид, то М — задача запишется:

Начальный опорный план X0 = (0, …, 0, b1, b2, …, bm).

Между оптимальным планом исходной задачи и оптимальным планом М-задачи существует следующая связь:

если в оптимальном плане М-задачи X*=(x1*, x2*, …, xn*, 1*, …, m*) все искусственные переменные равны 0, то план X*=(x1*, x2*, …, xn*) оптимален для исходной задачи.

Признак оптимальности начального опорного плана. Симплекс — таблицы.

Так как исходную задачу линейного программирования всегда можно представить в эквивалентом предпочтительном виде, то рассмотрим эту задачу в виде:

Решая ограничения — равенства относительно базисных переменных xi, и подставив их значения в целевую функцию, получим следующие равенства:

0 = c1b1+c2b2+…+cmbm=CбA0, где Cб — вектор коэффициентов целевой функции, стоящих у базисных переменных; А0 — вектор свободных элементов у системы ограничений, представленных в предпочтительном виде.

После подстановки в целевую функцию значений базисных переменных, выраженных через свободные переменные, получим:

Из данных выражений можно выяснить признак оптимальности опорного плана: при начальном опорном плане X0 = (b1, b2, …, bm, 0, …, 0) значение целевой функции Z (X0)= 0. Так как xj 0, при j0 целевая функция достигает минимума в точке X0. Если же j0, то в точке X0 целевая функция достигает максимума.

Значения j называют оценками свободных переменных.

Для решения задачи обычно данные заносят в таблицу, называемую симплекс-таблицей.

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

Пример. Модель задачи имеет вид:

min: Z=2×1-x2+3×3−2×4+x5 при ограничениях:

x2 + 0,5×3 + 0,5×5 = 1,5

Система ограничений данной задачи имеет предпочтительный вид. Заносим ее условие в симплекс-таблицу, где n+3 столбцов (n — число переменных в предпочтительном виде), m+2 строк, где m — число ограничений — равенств.

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

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

Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника; Ганнибалу, чтобы разбить римлян при Каннах, командуя вдвое меньшей армией, нужно было действовать очень обдуманно.

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

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

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

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

Читайте также: