Линейное программирование презентация. Презентация на тему "задачи линейного программирования"
Введение
Линейное программирование как раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программирования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса литературы по. линейному программированию в нашей стране выпущена в 60 - 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время.
Методы линейного программирования оказались весьма эффективными для решения некоторых задач из области исследования операций. Слово «программирование» мы понимаем как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении - как в местных, так и в государственных масштабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.
Математические методы и модели хорошо известны, распространены и используются под различными названиями - математические методы в принятии решений; методы исследования операций; экономико-математические методы; методы экономической кибернетики; методы оптимального управления, прикладная математика в экономике и организации производства и пр. Во множестве публикаций на данную тему (более или менее всеохватывающих) они рассматриваются в тех или иных сочетаниях.
Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.
Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций - количественное обоснование принимаемых решений по организации управления.
Целью всякого моделирования является исследование объекта вначале на качественном, а затем по мере накопления информации и развития модели на все более точных количественных уровнях.
Данные соображения могут быть проиллюстрированы простым примером. Существовал (и существует) метод «теория вероятностей» как широкий класс математических моделей, оперирующих понятиями «вероятность», «случайное событие», «случайная величина», «математические ожидание (среднее значение) случайной величины», «дисперсия (рассеяние)» и т. д. На границе XIX и XX вв. появляется новый объект - коммутируемая система телефонной связи, с которой ассоциируются понятия «заявка на соединение», «отказ», «время ожидания соединения», «коммутация» и другие характеристики системы.
В 20-е гг. А. К. Эрланг соединил эти метод и объект; в результате была создана математическая теоретико-вероятностная модель процессов в коммутируемых телефонных сетях, оперирующая понятиями «поток заявок», «среднее время ожидания», «средняя длина очереди на обслуживание», «дисперсия времени ожидания», «вероятность отказа» и т. д. Дальнейшее развитие этого научного направления показало плодотворность понятийной базы данной модели, ее широкие конструктивные возможности. Модель развилась в метод исследования сложных систем - «теорию массового обслуживания», терминология и понятийная база которого абстрагировались от ассоциаций с телефонными сетями и обрели общетеоретический характер. И теперь новые модели могут строиться путем применения теории массового обслуживания к другим объектам (производственные процессы, операционные системы ЭВМ, транспортные потоки и пр.).
Таким образом, с одной стороны, метод определен, если развита однородная совокупность моделей, т. е. способов рассмотрения различных объектов в одном аспекте, а с другой - объект познается тем глубже, чем больше моделей объекта разработано. При этом двойственная природа модели приводит к дуализму понятийной базы моделирования, включающей общие (от «метода») и специфичные (от «объекта») понятия.
Исследование операций - совокупность прикладных математических методов используемых для решения практических организационных (в том числе экономических) задач. Это - комплексная научная дисциплина. Круг проблем, изучаемых ею, недостаточно определен. Иногда исследование операций понимают очень широко, включая в него ряд чисто математических методов, иногда, наоборот, очень узко - как практическую методику решения с помощью экономико-математических моделей строго определенного перечня задач.
Главный метод исследования операций - системный анализ целенаправленных действий (операций) и объективная (в частности, количественная) сравнительная оценка возможных результатов этих действий.
Среди важнейших классов задач исследования операций можно назвать задачи управления запасами, распределения ресурсов и назначения (распределительные задачи), задачи массового обслуживания, задачи замены оборудования, упорядочения и согласования (в том числе теория расписаний), состязательные (например, игры), задачи поиска и др. Среди применяемых методов - математическое программирование (линейное, нелинейное и т. п.), дифференциальные и разностные уравнения, теории графов, Марковских процессов, теория игр, теория (статистических) решений, теория распознавания образов и ряд других.
Считается, что исследование операций зародилось накануне второй мировой войны, когда в Англии на одной радиолокационной станции была создана группа специалистов для решения технических задач с помощью математики. Они сосредоточили внимание на сравнении эффективности путей решения задач, поиске оптимального решения. Участие в этой группе представителей разных специальностей предопределило комплексный, или, как теперь принято говорить, системный, подход. В настоящее время в этом направлении работают сотни исследовательских учреждений и групп в десятках стран. Организованы общества исследования операций, объединяемые международной федерацией (ИФОРС).
В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В.Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие.
Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.
Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая нелинейные процессы линейными моделями, стохастические системы - детерминированными и т. д. Поэтому не следует ни преувеличивать значения количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Известно парадоксальное определение, которое дал крупный американский специалист в этой области
Т. А. Саати: «Исследование операций представляет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими способами».
ЦЕНТРАЛЬНЫЙ МЕЖРЕГИОНАЛЬНЫЙ ТЕХНИКУМ ОТРАСЛЕВЫХ ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛЬСТВА
Утверждаю
Зам. директора по учебной части
« » 200 г .
ЗАДАНИЕ
на курсовое проектирование
по предмету «Математические методы»
Студенту: Сергееву Евгению Анатольевичу.
Тема проекта: «Линейное программирование, решение задач симплексным методом».
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
- Введение
- Теоретическая часть
- Практическая часть
Задачи и их решение:
Задача первая:
Решить задачу симплекс методом:
F = 2X1 +3X2 → max
3.1.2 Задача вторая:
Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у. е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице:
3.1.3. Задача третья:
На предприятии выпускают 3 вида изделий, при этом используют 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:
Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
3.1.4. Задача четвертая:
Для изготовления 4 видов продукции используются 3 вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице:
Как следует спланировать выпуск продукции, чтобы прибыль была наибольшей?
3. Заключение
4. Список литературы
Председатель цикловой комиссии /Баранов В.А.
Руководитель курсового проекта /Карпушкин А.Г.
Дата выдачи задания: Срок окончания:
« » 2007 г. « » 2007 г.
СИМПЛЕКСНЫЙ МЕТОД
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако, еще в 1939 г. идеи метода были разработаны российским ученым
Л В.Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных
элемента:
Способ определения какого-либо первоначального допустимого
базисного решения задачи;
Правило перехода к лучшему (точнее, не худшему) решению;
Критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
Обыкновенные жордановы исключения
Рассмотрим систему из m линейных уравнений с n неизвестными
a11 x1 + a12 x2 + … + a1n xn = b1,
am1 x1 + am2 x2 + … + amn xn = bm.
Запишем эту систему в виде таблицы
a11 … a1j … a1n |
||
……………….. |
||
ai1 … aij … ain |
||
……………….. |
||
am1 … amj … amn |
Шагом обыкновенного жорданова исключения (ОЖИ), произведенным над данной таблицей с разрешающим элементом aij ≠ 0 с I разрешающей строкой и j разрешающим столбцом, назовем операцию решения уравнения
bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn
относительно xj, подстановки этого решения в исходную систему и записи вновь полученной системы в виде новой таблицы.
Нетрудно проверить, что новая таблица будет иметь вид
b11 b12 … a1j … b1n |
|||
b21 b22 … a2j … b2n |
|||
……………….. |
|||
Ai1 –ai2 … 1… -ain |
|||
……………….. |
|||
bm1 bm2 … amj … bmn |
где brs = ars aij - arj ais (i ≠ r, j ≠ s),
причем все элементы таблицы нужно разделить на aij .
Таким образом, один шаг жорданова исключения (ШЖИ) переводит исходную таблицу в новую по схеме, состоящей из следующих 5 правил:
1) разрешающий элемент заменяется единицей
2) остальные элементы разрешающего столбца j остаются без изменения.
3) остальные элементы разрешающей строки i меняют лишь свои знаки.
4) остальные элементы brs вычисляются по формуле brs = ars aij - arj ais
5) все элементы новой таблицы делятся на разрешающий элемент aij.
Пример 1. Для таблицы
Жордановы исключения позволяют от случайно взятой декартовой системы координатных плоскостей перейти к новой системе, в которой координатами точек являются их уклоненияот более интересной для той или другой задачи системы плоскостей.
Модифицированные жордановы исключения
Если исходную систему уравнений ai1 x1 + ai2 x2 + … + ain xn = bi, где i = 1,m,
записать в виде –ai1 (-x1) – ai2 (-x2) - … - ain (-xn) = bi
и составить таблицу
которая получается по правилам 1 – 5 ОЖИ с тем лишь изменением, что правила 2 и 3 меняются ролями:
1) остальные элементы разрешающей строки остаются без изменения
2) остальные элементы разрешающего столбца меняют лишь свои знаки
Рассмотрим систему
2X1 + 3X2 – 5X3 = 16 = b1,
3X1 - 2X2 + 4X3 = 36 = b2,
5X1 + 7X2 – 11X3 = 44 = b3 .
Запишем ее в виде таблицы
Экстремумы линейной функции
Пусть рассматривается общая задача линейного программирования. В основе вычислительных методов ЛП лежит следующая фундаментальная теорема.
Теорема. Если задача линейного программирования имеет оптимальное решение
(в ограниченной области всегда, а в неограниченной области в зависимости от ограниченности функции Z), то оно совпадает по крайней мере с одним из опорных решений системы ограничительных уравнений.
Согласно этой теореме вместо исследования бесконечного множества допустимых решений с целью нахождения среди них искомого оптимального решения, необходимо исследовать лишь конечное число опорных решений.
Данная теорема утверждает, что существует по крайней мере одно опорное оптимальное решение, однако, в задачах могут встретиться несколько опорных оптимальных решений (альтернативный оптимум).
Следовательно, принципиальная схема решения задач линейного программирования следующая:
1. С помощью ЖИ найдем все опорные решения системы.
a11 x1 + a12 x2 + … + a1n xn = b1 ,
……...................
ak1 x1 + ak2 x2 + … + akn xn = bk ,
ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1 ,
……...................
am1 x1 + am2 x2 + … + amn xn ≤ bm .
2. Вычислим для каждого из них значение функции Z, определяемое соотношением.
Z = c1 x1 + c2 x2 + … + cn xn.
3. Выберем из них экстремальное Z.
Следует отметить, что может оказаться очень большое число опорных решений, поэтому нужно производить упорядоченный перебор опорных решений, добиваясь на
каждом шаге монотонного изменения функции Z.
Такая идея последовательного улучшения решения и заложена в основном вычислительном методе решения задач линейного программирования, получившим название симплексного метода.
Симплексный метод на основе полных таблиц
Постановка задачи об определении оптимального ассортимента продукции
Предприятие может производить два вида изделий А и В, располагая для их изготовления ограниченными ресурсами материала чугуна и стали соответственно в количествах 350 и 392 кг и оборудования в количестве 408 станко-часов. Данные, представленные в виде таблицы, характеризуют затраты каждого из перечисленных трех видов ресурсов на изготовление одного изделия А и В.
Требуется определить сколько изделий А и В должно производить предприятие, чтобы достичь наибольшей прибыли.
Введем искомые неизвестные Х1 и X2, обозначающие число изделий А и В, которые должно производить предприятие.
Тогда математически задачу можно сформулировать следующим образом.
Среди множества неотрицательных решений системы неравенств
14X1 + 5Х2 ≤ 350, (1.1)
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
найти такое решение, для которого функция
Z = 10 Х1 + 5 Х2
достигает наибольшего значения.
Геометрическое решение задачи
Прежде всего, построим область допустимых решений, соответствующую системе неравенств.
Для этого, заменив каждое из неравенств равенством
14Х1 + 5Х2 = 350, (1-я прямая),
14X1 + 8Х2 = 392, (2-я прямая),
6Х1 + 12Х2 = 408, (3-я прямая),
строим граничную линию. Учитывая, что Х1 ≥ 0 и Х2 ≥ 0, получаем заштрихованную часть плоскости, образующую многоугольник решений OABCD (рис.1).
Затем строим линию уровня 10Х1 + 5Х2 = 0 и вектор (10;5), которые взаимно перпендикулярны. Нетрудно показать, что вектор дает направление наибольшего возрастания линейной функции.
Действительно
Z0= 10X10 + 5Х20 = 10 * 0 + 5 * 0 = 0,
ZА = 10X1A + 5Х2A = 10 * 0 + 5 * 34 = 170,
ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 и т. д.
Из всех линий уровня выбираем две, из которых одна проходит через точку 0 и дает min значение функции Z, а другая проходит через точку С и функция Z для нее принимает mах значение. Эти линии уровня называются опорными.
Рис. 1
Точка C образована первой и второй прямыми. Следовательно, решая систему уравнений
14Хl + 5Х2 = 350,
14Х1 + 8Х2 = 392,
найдем координаты точки C
Х1 = 20, Х2 = 14,
при этом Zmax = 10 * 20 + 5 * 14 = 270 руб.
Таким образом, mах прибыль в 270 руб. будет получена, если предприятие произведет 20 изделий вида А и 14 изделий вида В.
Отыскание максимума линейной функции
В основе симплексного метода решения задач линейного программирования лежит с некоторыми дополнениями разобранный ранее метод последовательных исключений, представляющий собой совокупность удобных вычислительных алгоритмов, построенных на последовательном применении тождественных (симплексных) преобразований системы уравнений.
Добавляя к левой части неравенств
14X1 + 5Х2 ≤ 350,
14Х1 + 8Х2 ≤ 392,
6Х1 + 12Х2 ≤ 408,
некоторую неотрицательную величину Yj ≥ 0 (i = 1, 2, 3), (1.2)
называемую выравнивающей или базисной переменной, превратим их в уравнения:
Х1 + 5Х2 + У1 | |||
При этом можно показать, что каждому решению системы неравенств (1.1) соответствует единственное решение системы уравнений (1.3) и неравенств (1.2) и наоборот.
Каждая из переменных Y1, У2, У3 входит только в одно уравнение и зависит от переменных Х1 и X2, которые мы называем свободными.
Системе (1.3) соответствует исходное допустимое базисное решение X1 = X2 = 0;
Y1 = 350; Y2 = 392; Y3 = 408 и Z = 0.
Выполняем первое тождественное преобразование системы уравнений (1.3). Выбираем разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z строке, ибо теоретически установлено, что при этом можно ожидать при прочих равных условиях большего увеличения функции Z. Правую часть уравнений делим на элементы разрешающего столбца и выбираем наименьшее положительное отношение, соответствующее разрешающей строке (уравнению). На пересечении выделенных столбца и строки стоит разрешающее число.
Первое уравнение делим на разрешающее число и выписываем получившееся уравнение. Умножая это уравнение на 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (1.3), придем к следующей системе (1.4):
X2 + 1/4 Y1 = 25, |
||
X2 – 6/14 Y1 + У3 | ||
Подобное тождественное преобразование, при котором выбор разрешающего числа производится по указанному правилу, будем называть симплексным преобразованием.
Таким образом, симплексное преобразование выполняется по следующему правилу:
1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z - строке.
2. Выбирается разрешающая строка, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца. На пересечении разрешающего столбца и разрешающей строки стоит разрешающее число.
3. Элементы разрешающей строки делятся на разрешающее число.
4. Вычисляются элементы всех остальных строк по формуле:
Из системы (1.4) находим второе допустимое базисное решение Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, которому соответствует новое увеличенное значение функции Z = 250.
Таким образом, процесс последовательных симплексных преобразований является процессом последовательного улучшения решения. При этом:
1. Если в Z - строке найдется хотя бы один отрицательный элемент и
а) в разрешающем столбце найдется хотя бы один положительный элемент, то можно улучшить решение;
б) если же разрешающий столбец не содержит положительных элементов, то функция Z неограниченно возрастает.
2. Если все элементы в Z - строке неотрицательны, то достигнуто оптимальное решение.
Это и есть достаточные условия существования оптимального плана решения.
В системе (1.4) коэффициент при Х2 в Z - строке отрицательный, поэтому второй столбец будет разрешающим. Находим, что вторая строка будет разрешающей. Далее производим симплексное преобразование системы (1.4) согласном указанному правилу:
X1 + 8/42 Y1 – 5/42 Y2 = 20,
X2 – 1/3 Y1 + 1/3 Y2 = 14,
20/7 Y1 – 23/7 Y2 + Y3 = 120,
10/42 Y1 + 20/42 Y2 + Z = 270, (1.5)
Так как в Z - строке все элементы неотрицательны, то данный план является оптимальным. При этом Yl = Y2 = 0; X1 = 20; Х2 = 14 и Zmax = 270.
Выполнение симплексных преобразований связано с кропотливыми и часто довольно громоздкими вычислениями. Эти вычисления можно в значительной степени упростить, используя для решения задач так называемые симплексные таблицы.
Каждое симплексное преобразование системы сводится к переходу от одной симплексной таблицы к другой.
Соответственно исходной системе уравнений (1.3) составляем первую симплекс-таблицу (табл. 1.1).
Таблица 1.1
Первый столбец - это столбец базисных переменных, во втором столбце стоят свободные коэффициенты правой части уравнений (1.3), в первой строке располагаются все переменные, последний столбец - это контрольный столбец и коэффициенты в нем равны сумме всех коэффициентов по строке.
Из табл. 1.1 имеем первое допустимое решение системы (1.3) Х1 = Х2 = 0, Y1 = 350,
Y2 = 392, Y3 = 408, Z = 0, которое соответствует вершине О (0,0) многоугольника допустимых решений OABCD (рис.1).
Переход ко второй симплекс-таблице (табл. 1.2) выполняется согласно указанному в этом пункте правилу для симплексных преобразований систем уравнений, при этом разрешающая переменная Х1 идет в базис вместо разрешающей переменной Y1 Получаем табл. 1.2.
Таблица 1.2
После заполнения табл. 1.2 следует проверить правильность ее заполнения, для чего суммируем коэффициент по строкам и эта сумма должна быть равна коэффициентам, стоящим в соответствующих клетках контрольного столбца. Из табл. 1.2 второе допустимое решение будет Х1 = 25, Х2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 и Z = 250.
Нетрудно видеть, что эта таблица соответствует системе (1.4), а опорное решение
Х1 = 25, Х2 = 0 соответствует вершине D(25,0) многоугольника решений.
Так как в Z - строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. 1.3.
Таблица 1. 3
* Примечание. Для простоты вычислений следует помнить, что в новой таблице на месте элементов разрешающего столбца (кроме разрешающего элемента) стоят нули. Если в разрешающей строке стоят нули, то в новую таблицу соответствующие столбцы переносятся без изменения:
Так как в Z - строке нет отрицательных элементов, то данное решение будет оптимальным.
Табл. 1.3 соответствует системе уравнений (1.5) и оптимальному решению Х1 = 20,
Х2 = 14 и Zmax = 270 и вершине С (20,14) многоугольника допустимых решений OABCD.
Подобные удлиненные таблицы, содержащие в первой строке все переменные, благодаря наличию контрольного столбца позволяют контролировать правильность заполнения таблиц и избежать арифметических ошибок.
Симплексный метод на основе укороченных таблиц
Рассмотрим систему уравнений (1.3) и запишем ее в виде таблицы 1.4
Таблица 1.4
В первый столбец записываем базисные переменные (БП), а в первую строку – свободные переменные (СП). Далее переход к новой таблице 1.5 совершаем по правилу:
1) меняем местами СП и БП
2) на месте разрешающего элемента стоит величина ему обратная
3) элементы разрешающей стоки делим на разрешающее число
4) элементы разрешающего столбца делим на разрешающее чисто и меняем знак
5) остальные элементы находятся как в главе “Отыскание максимума линейной функции” правило 4 (правило прямоугольников для ОЖИ). Получаем таблицу 1.5.
Таблица 1.6
Получили оптимальный план Zmax = 270 при X1 =20, X2 = 14, а ресурсы оборудования оказались в избытке в количестве 120 станко–часов.
Решение задачи линейного программирования
Найти максимум целевой функции
при ограничениях
14x + 5y ≤ 350
Решение задачи с использованием программы Microsoft Excel.
Отведем А3 и B3 под значения переменных x и y.
В ячейку C4 введем функцию цели
В ячейки A7:A9 введем левые части ограничений
а в ячейки B7:B9 – правые части ограничений.
После этого выберем команду Сервис , Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения ( Solver) как показано на рис. 2. После нажатия кнопки Выполнить (Solve) открывается окно Результаты поиска решения (Solver Results), которое сообщает, что решение найдено (рис. 3).
Рис. 2. Поиск решения
Рис. 3. Результаты поиска решения
Геометрическое решение задачи с применением программы MATHCAD 2000.
- Запишите в виде y = kx + b уравнения прямых, ограничивающих область допустимых значений переменных. Для того чтобы ввести и разрешить относительно y ограничение 14x + 5y ≤ 350, введите левую часть неравенства, нажмите кнопку Ctrl и нажмите одновременно кнопку =, удерживая предыдущую до тех пор пока выскочит жирный знак =, пометьте выделяющей рамкой переменную y, щелкните в меню Symbolic (Символы) по строке Solve (Вычислить) – результат вычислений будет выведен в рабочем документе справа от уравнения; введите имя функции (в рассматриваемом примере y1(x)) и присвойте ей полученное выражение. Таким образом, определено уравнение одной из прямых, ограничивающих область допустимых значений. Аналогично введите остальные ограничения. Введите уравнение 10x + 5y = C линии уровня (опорная прямая) целевой функции. Действуйте так же, как и при вводе ограничений, но перед тем как разрешить уравнение относительно y, присвойте какое-нибудь значение константе C.
- Изобразите на графике соответствующие прямые и определите область допустимых решений системы.
- Изменяя значения константы C, например C = 100,150,200,250,..., наблюдайте за движением опорной прямой и сформулируйте вывод о разрешимости задачи.
- Если задача имеет единственное решение, найдите вершину, в которой Z = Zmax. В нашем примере максимум целевой функции достигается в точке пересечения прямых 14x + 5y = 350 и 7x + 14y = 196. Найдите координаты точки, используя функцию Find.
- Вычислите значение целевой функции в найденной точке.
14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70
7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49
x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34
10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C
Рис. 4.
Найти (x, y) → (20, 14)
f(x, y): = 10x + 5y
fmin: = f(20, 14)
Аналитическое решение задачи с применением программы MATHCAD 2000.
Аналитическое решение задачи в MathCAD значительно проще.
- Установите режим автоматических вычислений.
- Запишите задачу произвольным x и y присвойте произвольные (допустимые) значения, чтобы программа могла начать счет.
Z(x, y): = 10x + 5y
14x + 5x ≤ 360
M: = Максимизировать (z, x, y) M = (20, 14) Z (M0, M1) = 270
Задача максимизации линейной функции при наличии отрицательных свободных коэффициентов
Найти максимум линейной функции
при ограничениях
X1 – X2 ≤ 3,
2X1 – 3X2 ≤ 6,
X1 ≥ 0, X2 ≥ 0.
Запишем систему в виде
Y1 = -X1 + X2 + 3 ≥ 0
Y2 = X1 + X2 - 5 ≥ 0
Y3 = -2X1 + 3X2 + 6 ≥ 0
Y4 = -X2 + 6 ≥ 0
Составим таблицу.
Продолжаем работать со 2-й строкой, так как отрицательный элемент не пропал. Совершаем ШМЖИ с разрешающим элементом -2. Получаем таблицу.
Задача минимизации линейной функции
Сведение задачи минимизации к задаче максимизации линейной функции
Мы рассматривали решение симплекс-методом задачи отыскания максимума линейной функции
W = c1 x1 + c2 x2 + … + cn xn.
Однако во многих экономических задачах требуется найти минимум линейной функции. Для этого достаточно положить
W = -Z = -c1 x1 – c2 x2 - … - cn xn
и решать задачу максимизации полученной функции W при соответствующих ограничениях. Так как ясно, что
Минимизировать линейную функцию
при выполнении ограничений
7X1 + 2X2 ≥ 14,
5X1 + 6X2 ≤ 30,
3X1 + 8X2 ≥ 24,
X1 ≥ 0, X2 ≥ 0.
Геометрическое решение задачи на (рис. 5) и ему отвечает оптимальное решение в точке
С (48/11, 15/11) и при этом Zmin = -21/11.
Рис 5. Геометрическое решение задачи
Вводя выравнивающие переменные Yi ≥ 0 и функцию W = -Z = 2X1 - 5X2 → max, задачу запишем в виде.
Y1 = 7X1 + 2X2 - 14,
Y2 = -5X1 - 6X2 + 30,
Y3 = 3X1 + 8X2 - 24,
Записываем эту систему в виде таблицы.
Избавляемся от отрицательного свободного члена в Y1 – строке, совершая ШМЖИ с разрешающим элементом “-50/8”, получаем таблицу.
Так как в W – строке и в 1 – столбце нет отрицательных элементов, то получили оптимальное решение X1 = 48/11, X2 = 15/11, Wmax – 21/11 или Zmin = –Wmax = -21/11,
Практическая часть
1. Решить задачу симплекс методом.
X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → max
Решение
X1 + 3X2 + X3 = 300 F - 2X1 - 3X2 = 0
X1 + X2 + X4 = 150
Ответ: X1 = 75; X2 = 75; X3 = 0; X4 = 0.
Задача №1.
Предприятие выпускает продукцию двух видов. Виды сырья, его запасы, нормы расхода сырья на у.е. каждого вида продукции, прибыль производства от реализации продукции даны в таблице.
Решение
2X1 + 2X2 ≤ 17
X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0
2X1 + X2 + X4 = 10
2X1 + 2X2 + X5 =17
Ответ: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7.
Задача №2.
На предприятии выпускается три вида изделий, при этом используется три вида сырья. Запасы сырья, нормы его расхода и прибыль от реализации каждого продукта приведены в таблице.
Как следует спланировать выпуск продукции, чтобы прибыль предприятия была наибольшей?
Решение
2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → max
5X1 + 3X2 ≤ 900
2X1 + 3X2 + 7X3 + X4 = 1250 F - 41X1 - 35X2 - 96X3 = 0
X1 +X2 + X5 = 250
5X1 +3X2 + X6 = 900
X1 + 3X2 ≤ 20 F = 2X1 + X2 → max
2X1 + 2X2 ≤ 17
(-1/3)(-1/3)(2/3)
Ответ: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5.
Заключение
Остановимся на простейших истолкованиях симплексного метода.
Алгебраический смысл симплексного метода состоит в том, что, совершая тождественные алгебраические преобразования, мы переходим от одного допустимого решения системы алгебраических уравнений к другому улучшенному, достигая оптимального решения задачи.
С геометрической точки зрения тождественные преобразования по симплексному методу представляют собой последовательные движения от одной вершины выпуклого многоугольника решений к соседней, от нее к следующей и так к оптимальной вершине по сторонам этого многоугольника.
Экономическая сущность симплексного метода заключается в том, что он является методом последовательного улучшения решений. Этот метод дает возможность, выбрав отправной – опорный план действий, постепенно передвигаться вперед и в конечном итоге достичь оптимальный план, если, конечно, такой существует.
Симплекс – выпуклый многоугольник в n – мерном пространстве с n + 1 вершинами, не лежащими на одной гиперплоскости. Симплексы выделены в отдельный класс потому, что симплекс – это простейший многоугольник, содержащий некоторый объем n – мерного пространства.
Доказано, что если оптимальное решение существует то оно обязательно будет найдено через конечное число шагов (за исключением так называемой “вырожденной задачи”, при которой возможно явление “зацикливания”, т.е. многократного возврата к одному и тому же положению).
Линейное программирование - область математического программирования, посвященная теории и методам решения экстремальных задач, характеризующихся линейной зависимостью между переменными.
Математическое программирование (оптимальное программирование) – область математики, объединяющая различные математические методы и дисциплины: линейное программирование, динамическое программирование, выпуклое программирование и др. Общая задача математического программирования состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
Список использовавшейся литературы
1) А. С. Шапкин, Н. П. Мазаева; Математические методы и модели исследования операций , 2005.
2) Н.Ш. Кремер, Б А Путко, И.М. Тришин, М.Н. Фридман ; Исследование операций в экономике . - ЮНИТИ, 2002.
Линейное программирование▪ Задача линейного программирования – 3 слайд.
▪ Геометрический метод решения ЗЛП – 26 слайд.
▪ Задача линейного программирования в стандартной форме – 32 слайд.
▪ Симплексный метод решения ЗЛП – 42 слайд.
▪ Метод Гаусса – 48 слайд.
▪ Симплекс метод – 58 слайд.
▪ Метод искусственного базиса – 76 слайд.
▪ Двойственность задач линейного программирования – 87 слайд.
Задача линейного программирования (ЛП)
▪Задачи ЛП – самая обширная часть оптимизационных (примерно 70%)
Этапы построения математической модели
1. Определение переменных задачи.2. Представление ограничений в виде линейных уравнений
или неравенств.
3. Задание линейной целевой функции и смысла
оптимизации.
Классические задачи линейного программирования
▪ Задача технического контроля (слайд 6);▪ Транспортная задача (слайд 13);
▪ Задача о диете (слайд 16);
▪ Задача об использовании сырья (слайд 19).
Задача технического контроля
Примечание: ОТК – Отдел Технического Контроля В ОТК некоторой фирмы работают контролеры 1 и 2 разрядов (К1 иК2);
Норма выработки ОТК за 8 часов (раб. день) составляет не менее
1800 изделий;
К1 проверяет 25 изделий/час (точность 98%);
К2 проверяет 15 изделий/час (точность 95%);
Заработная плата К1 равна 4$ / час;
Заработная плата К2 равна 3$ / час;
При каждой ошибке контролера фирма несет убыток в 2$;
Фирма может использовать не более 8 - К1 и 10 - К2;
Определить оптимальный состав ОТК,
при котором общие затраты на контроль будут минимальны.
Принятие решений в условиях неопределенности Если первый субъект имеет m стратегий, а второй - n стратегий, то говорят, что мы имеем дело с игрой m x n. Рассмотрим игру m x n. Пусть заданы множество стратегий: для первого игрока {Аi}, для второго игрока {Bj}, платежная матрица, где aij – выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi и Bj соответственно. Каждый из игроков выбирает однозначно с вероятностью I некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш. Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком проводится при полном отсутствии информации о принимаемом решении вторым игроком.
Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.
Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"
Подобные документы
-
Слайд 14
Допустим, что будет изготовлено изделий вида А, -изделий вида В и -изделий вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство
Слайд 15
Рассуждая аналогично, можно составить систему ограничений
Слайд 16
Теперь составим целевую функцию. Прибыль от реализации изделий вида А составит 10 , от реализации -изделий вида В -14 и от реализации -изделий вида С-12 Общая прибыль от реализации всех изделий составит
Слайд 17
Таким образом, приходим к следующей ЗЛП: Требуется среди всех неотрицательных решений системы неравенств найти такое, при котором целевая функция принимает максимальное значение.
Слайд 18
Пример 2
Продукцией гормолокозавода являются молоко, кефир и сметана, расфасованные в тару. На производство 1 т молока, кефира и сметаны требуется соответственно1010,1010 и 9450 кг молока. При этом затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часов.
Слайд 19
Всего для производства цельномолочной продукции завод может использовать 136000 кг молока. Основное оборудование может быть занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 30, 22 и 136 руб. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки. На производство другой продукции нет ограничений.
Слайд 20
Требуется определить, какую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной. Составить математическую модель задачи.
Слайд 21
Решение
Пусть завод будет производить т молока, т кефира и т сметаны. Тогда ему необходимо кг молока. Так как завод может использовать ежедневно не более 136000 кг молока, то должно выполняться неравенство
Слайд 22
Ограничения на время по расфасовке молока и кефира и по расфасовке сметаны. Так как ежедневно должно вырабатываться не менее100 т молока, то. По экономическому смыслу
Слайд 23
Общая прибыль от реализации всей продукции равна руб. Таким образом, приходим к следующей задаче: при ограничениях Так как целевая функция линейная и ограничения заданы системой неравенств, то эта задача является ЗЛП.
Слайд 24
Задача о смесях.
Имеетсядва вида продукции, содержащие питательные вещества (жиры, белки и т.д.)
Слайд 25
Таблица
-
Слайд 26
Решение
Общая стоимость рациона при ограничениях с учетом необходимого минимума питательных веществ
Слайд 27
Математическая постановка задачи: составить дневной рацион, удовлетворяющий системе ограничений и минимизирующий целевую функцию. В общем виде к группе задач о смесях относятся задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Полученные смеси должны иметь в своем составе nразличных компонентов в определенных количествах, а сами компоненты являются составными частями m исходных материалов.
Слайд 28
Введем обозначения: -количество j-го материала, входящего в смесь; -цена материала j-го вида; -это минимально необходимое содержание i-го компонента в смеси. Коэффициенты показывают удельный вес i-го компонента в единице j-го материала
Слайд 29
Экономико-математическая модель задачи.
Целевая функция представляет собой суммарную стоимость смеси, а функциональные ограничения являются ограничениями по содержанию компонентов в смеси: смесь должна содержать компоненты в объемах, не менее указанных.
Слайд 30
Задача о раскрое
На швейной фабрике ткань может быть раскроена несколькими способами для изготовления нужных деталей швейных изделий. Пусть при j-ом варианте раскроя изготавливается деталей i-го вида, а величина отходов при данном варианте раскроя равна Зная, что деталей i-го вида следует изготовлять штук, требуется раскроить ткань так, чтобы было получено необходимое количество деталей каждого вида при минимальных общих отходах. Составить математическую модель задачи.
Слайд 31
Решение. Предположим, что по j-ому варианту раскраивается сотен ткани. Поскольку при раскрое ткани по j-ому варианту получается деталей i-го вида, по всем вариантам раскроя из используемых тканей будет получено Общая величина отходов по всем вариантам раскроя составит
Слайд 35
Основная задача ЛП
Опр.4. Основной, или канонической ЗЛП называется задача, состоящая в определении значения целевой функции при условии, что система ограничений представлена в виде системы уравнений:
Слайд 36
Если требуется для удобства или по смыслу задачи перейти от одной формы записи к другой, то поступают следующим образом. Если требуется найти минимум функции, то можно перейти к нахождению максимума, умножив целевую функции на (-1). Ограничение –неравенство вида можно преобразовать в равенство добавлением к его левой части неотрицательной дополнительной переменной, а ограничение неравенство вида - в ограничение- равенство вычитанием из его левой части дополнительной неотрицательной переменной.
Слайд 41
Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным. План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное) значение, называется оптимальным.
Посмотреть все слайды
Задачи оптимизации. Ограничения на допустимое множество. Классическая задача оптимизации. Функция Лагранжа. Линейное программирование: формулировка задач и их графическое решение. Алгебраический метод решения задач. Симплекс-метод, симплекс-таблица.
реферат , добавлен 29.09.2008
Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа , добавлен 27.03.2011
Общие задачи линейного программирования. Описание алгоритма симплекс-метода, записанного в канонической форме с односторонними ограничениями. Алгоритм построения начального опорного плана для решения задачи. Расширенный алгоритм искусственного базиса.
курсовая работа , добавлен 24.10.2012
Математические основы оптимизации. Постановка задачи оптимизации. Методы оптимизации. Решение задачи классическим симплекс методом. Графический метод. Решение задач с помощью Excel. Коэффициенты целевой функции. Линейное программирование, метод, задачи.
реферат , добавлен 21.08.2008
Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа , добавлен 05.01.2015
Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа , добавлен 11.02.2011
Понятие теории оптимизации экономических задач. Сущность симплекс-метода, двойственности в линейном программировании. Элементы теории игр и принятия решений, решение транспортной задачи. Особенности сетевого планирования и матричное задание графов.
Слайд 2
Линейное программирование
Методы линейного программирования используют в прогнозных расчетах, при планировании и организации производственных процессов. Линейное программирование – это область математики, в которой изучаются методы исследования и отыскания экстремальных значений некоторой линейной функции, на аргументы которой наложены линейные ограничения.
Слайд 3
Такая линейная функция называется целевой, а набор количественных соотношений между переменными, выражающих определенные требования экономической задачи в виде уравнений или неравенств, называется системой ограничений. Слово программирование введено в связи с тем, что неизвестные переменные обычно определяют программу или план работы некоторого субъекта.
Слайд 4
Совокупность соотношений, содержащих целевую функцию и ограничения на ее аргументы, называется математической моделью задачи оптимизации. ЗЛП записывается в общем виде так: при ограничениях
Слайд 5
Здесь -неизвестные, -заданные постоянные величины.Ограничения могут быть заданы уравнениями. Наиболее часто встречаются задачи в виде: имеется ресурсов при ограничениях. Нужно определить объемы этих ресурсов, при которых целевая функция будет достигать максимума (минимума), т. е. найти оптимальное распределение ограниченных ресурсов. При этом имеются естественные ограничения >0.
Слайд 6
При этом экстремум целевой функции ищется на допустимом множестве решений, определяемом системой ограничений, причем все или некоторые неравенства в системе ограничений могут быть записаны в виде уравнений.
Слайд 7
В краткой записи ЗЛП имеет вид: при ограничениях
Слайд 8
Для составления математической модели ЗЛП необходимо: 1)обозначить переменные; 2)составить целевую функцию; 3)записать систему ограничений в соответствии с целью задачи; 4)записать систему ограничений с учетом имеющихся в условии задачи показателей. Если все ограничения задачи заданы уравнениями, то модель такого вида называется канонической. Если хоть одно из ограничений дано неравенством, то модель неканоническая.
Слайд 9
Примеры задач, которые сводятся к ЗПЛ.
задача оптимального распределения ресурсов при планировании выпуска продукции на предприятии (задача об ассортименте); задача на максимум выпуска продукции при заданном ассортименте; задача о смесях (рационе, диете и т.д.); транспортная задача; задача о рациональном использовании имеющихся мощностей; задача о назначениях.
Слайд 10
1.Задача оптимального распределения ресурсов.
Предположим, что предприятие выпускает различных изделий. Для их производства требуется различных видов ресурсов (сырья, рабочего и машинного времени, вспомогательных материалов). Эти ресурсы ограничены и составляют в планируемый период условных единиц. Известны также технологические коэффициенты, которые указывают, сколько единиц i-го ресурса требуется для производства изделия j-го вида. Пусть прибыль, получаемая предприятием при реализации единицы изделия j-го вида, равна. В планируемый период все показатели предполагаются постоянными.
Слайд 11
Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей. Экономико-математическая модель задачи
Слайд 12
Целевая функция представляет собой суммарную прибыль от реализации выпускаемой продукции всех видов. В данной модели задачи оптимизация возможна за счет выбора наиболее выгодных видов продукции. Ограничения означают, что для любого из ресурсов его суммарный расход на производство всех видов продукции не превосходит его запасы.
Слайд 13