Презентация графического метода линейного программирования. Презентация на тему «Тема «Линейное программирование

Введение

Линейное программирование как раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программи­рования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса лите­ратуры по. линейному программированию в нашей стране выпущена в 60 - 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время.

Методы линейного программирования оказались весьма эффектив­ными для решения некоторых задач из области исследования операций. Слово «программирование» мы понимаем как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и управлении - как в местных, так и в государственных мас­штабах. Этими методами можно решить многие (хотя не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

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

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

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

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

Данные соображения могут быть проиллюстрированы про­стым примером. Существовал (и существует) метод «теория ве­роятностей» как широкий класс математических моделей, опе­рирующих понятиями «вероятность», «случайное событие», «случайная величина», «математические ожидание (среднее зна­чение) случайной величины», «дисперсия (рассеяние)» и т. д. На границе XIX и XX вв. появляется новый объект - коммутируе­мая система телефонной связи, с которой ассоциируются поня­тия «заявка на соединение», «отказ», «время ожидания соедине­ния», «коммутация» и другие характеристики системы.

В 20-е гг. А. К. Эрланг соединил эти метод и объект; в резуль­тате была создана математическая теоретико-вероятностная мо­дель процессов в коммутируемых телефонных сетях, оперирующая понятиями «поток заявок», «среднее время ожидания», «средняя длина очереди на обслуживание», «дисперсия времени ожидания», «вероятность отказа» и т. д. Дальнейшее развитие это­го научного направления показало плодотворность понятийной базы данной модели, ее широкие конструктивные возможности. Модель развилась в метод исследования сложных систем - «тео­рию массового обслуживания», терминология и понятийная база которого абстрагировались от ассоциаций с телефонными сетями и обрели общетеоретический характер. И теперь новые модели могут строиться путем применения теории массового обслужива­ния к другим объектам (производственные процессы, операцион­ные системы ЭВМ, транспортные потоки и пр.).

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

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

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

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

Считается, что исследование операций зародилось накануне второй мировой войны, когда в Англии на одной радиолокаци­онной станции была создана группа специалистов для решения технических задач с помощью математики. Они сосредоточили внимание на сравнении эффективности путей решения задач, поиске оптимального решения. Участие в этой группе предста­вителей разных специальностей предопределило комплексный, или, как теперь принято говорить, системный, подход. В настоя­щее время в этом направлении работают сотни исследователь­ских учреждений и групп в десятках стран. Организованы обще­ства исследования операций, объединяемые международной фе­дерацией (ИФОРС).

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л.В.Канторович, Н.П. Бусленко, Е.С. Вентцель, Н.Н. Воробьев, Н.Н. Моисеев, Д.Б. Юдин и многие другие.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черчмен, А. Кофман и др.

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

Т. А. Саати: «Исследование операций представля­ет собой искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими спо­собами».

ЦЕНТРАЛЬНЫЙ МЕЖРЕГИОНАЛЬНЫЙ ТЕХНИКУМ ОТРАСЛЕВЫХ ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛЬСТВА

Утверждаю

Зам. директора по учебной части


« » 200 г .

ЗАДАНИЕ

на курсовое проектирование

по предмету «Математические методы»

Студенту: Сергееву Евгению Анатольевичу.

Тема проекта: «Линейное программирование, решение задач симплексным методом».

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

  1. Введение
  2. Теоретическая часть
  3. Практическая часть

Задачи и их решение:

Задача первая:

Решить задачу симплекс методом:

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.

  1. Запишите в виде y = kx + b уравнения прямых, ограничивающих область допустимых значений переменных. Для того чтобы ввести и разрешить относительно y ограничение 14x + 5y ≤ 350, введите левую часть неравенства, нажмите кнопку Ctrl и нажмите одновременно кнопку =, удерживая предыдущую до тех пор пока выскочит жирный знак =, пометьте выделяющей рамкой переменную y, щелкните в меню Symbolic (Символы) по строке Solve (Вычислить) – результат вычислений будет выведен в рабочем документе справа от уравнения; введите имя функции (в рассматриваемом примере y1(x)) и присвойте ей полученное выражение. Таким образом, определено уравнение одной из прямых, ограничивающих область допустимых значений. Аналогично введите остальные ограничения. Введите уравнение 10x + 5y = C линии уровня (опорная прямая) целевой функции. Действуйте так же, как и при вводе ограничений, но перед тем как разрешить уравнение относительно y, присвойте какое-нибудь значение константе C.
  2. Изобразите на графике соответствующие прямые и определите область допустимых решений системы.
  3. Изменяя значения константы C, например C = 100,150,200,250,..., наблюдайте за движением опорной прямой и сформулируйте вывод о разрешимости задачи.
  4. Если задача имеет единственное решение, найдите вершину, в которой Z = Zmax. В нашем примере максимум целевой функции достигается в точке пересечения прямых 14x + 5y = 350 и 7x + 14y = 196. Найдите координаты точки, используя функцию Find.
  5. Вычислите значение целевой функции в найденной точке.

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 значительно проще.

  1. Установите режим автоматических вычислений.
  2. Запишите задачу произвольным 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;
Определить оптимальный состав ОТК,
при котором общие затраты на контроль будут минимальны.

Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com


Подписи к слайдам:

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

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

Задача. Имеется 14 каналов радиорелейной связи (РРС) и 9 каналов тропосферной. По ним необходимо передать информацию 3 видов: А, В, С. Причем информация А равна 600 у.е., В – 3000 у.е., С – 5500 у.е. (под информацией можно понимать число телефонных разговоров, передачу данных и пр.). Возможности каналов и затраты на обслуживание каждого канала заданы в таблице. Требуется отыскать задействованное количество каналов обоих видов, необходимое для передачи требуемой информации, чтобы стоимость эксплуатации была минимальной.

Виды информации Каналы связи Требуемое количество информации, у.ед. Тропосферная РРС А 80 40 600 В - 1000 3000 С 300 800 5500 Затраты на обслуживание одного канала, руб. 3000 2000

Этапы решения ЗЛП: Построить ОДР. Построить вектор-градиент целевой функции в какой-нибудь точке Х 0 принадлежащей ОДР – (c 1 ;c 2) . Построить прямую c 1 x 1 + c 2 x 2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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


По теме: методические разработки, презентации и конспекты

Данная разработка может применяться как обобщающий урок по теме "Системы неравенств с двумя переменными" в 9 классе (алгебра 9 под ред. Теляковского) и как урок повторения по данной теме в 10 классе. ...

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

Рабочая тетрадь к уроку математики на тему «Задачи линейного программирования» разработана мною для одноимённого урока математики (повышенный уровень). может быть использована как на уроке, семинарско...

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

Неравенства

Линейные неравенства – это неравенства вида ∑ai xi +b≥c

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

Начиная с середины 40-х годов этого столетия, возникла новая область прикладной математики – линейное программирование – с важными приложениями в экономике и технике. В конечном счете линейное программирование – это всего лишь один из разделов (хотя и очень важный) теории систем линейных неравенств.

Рассмотрим уравнение первой степени с двумя неизвестными x и y

Истолковывая x и y как координаты точки

на плоскости, можем сказать, что

множество точек, определяемых уравнением (1), есть прямая линия на плоскости.

Геометрический смысл уравнения первой степени

Аналогично для неравенства ax+by+c≥0. (2)

Если b≠0, то данное неравенство приводится к одному из видов у≥kх+p или у≤kх+р.

Первому из этих неравенств удовлетворяют все точки, лежащие «выше» прямой у=kх+р или же на этой прямой, а второму – все точки, лежащие «ниже» прямой у=kх+р или на этой прямой.

Если же b=0, то неравенство приводится к одному из видов х≥h или х≤h. Первому из них удовлетворяют все точки, лежащие «правее» прямой х=h или на этой прямой, второму – все точки, лежащие «левее» прямой х=h или на этой прямой.

Геометрический смысл системы линейных неравенств

Пусть дана система неравенств с двумя неизвестными х и у. a1 x+b1 y+c1 ≥0,

a2 x+b2 y+c2 ≥0,

………….........

am x+bm y+cm ≥0.

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

Пример

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

Неограниченная область решений

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

Описание презентации по отдельным слайдам:

1 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Линейное программирование К этому классу линейного программирования (75% решаемых американцами задач) относятся задачи, в которых целевая функция Wm(x), m=1,2,...,M, ограничения в виде равенств hk(x)=0, k=1,2...K, и неравенств gj(x)>0, j=1,2,...J, - линейны и нет математического решения. Возможные тематики задач ЛП: рациональное использование сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; на составление оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Постановка задачи ЛП (определение показателя эффективности, переменных задачи, задание линейной целевой функции W(x), подлежащей минимизации или максимизации, функциональных hk(x), gj(x) и областных xli

2 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Пример задачи ЛП Пример – Оптимизация размещения побочного производства лесничества Лесничество имеет 24 га свободной земли под паром и заинтересовано извлечь из нее доход. Оно может выращивать саженцы быстрорастущего гибрида новогодней ели, которые достигают спелости за один год, или бычков, отведя часть земли под пастбище. Деревья выращиваются и продаются в партиях по 1000 штук. Требуется 1.5 га для выращивания одной партии деревьев и 4 га для вскармливания одного бычка. Лесничество может потратить только 200 ч. в год на свое побочное производство. Практика показывает, что требуется 20 ч. для культивации, подрезания, вырубки и пакетирования одной партии деревьев. Для ухода за одним бычком также требуется 20 ч. Лесничество имеет возможность израсходовать на эти цели 6 тыс. руб. Годовые издержки на одну партию деревьев выливаются в 150 руб. и 1,2 тыс. руб. на одного бычка. Уже заключен контракт на поставку 2 бычков. По сложившимся ценам, одна новогодняя ель принесет прибыль в 2,5 руб., один бычок - 5 тыс. руб.

3 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Постановка задачи 1. В качестве показателя эффективности целесообразно взять прибыль за операцию (годовую прибыль с земли в рублях). 2. В качестве управляемых переменных задачи следует взять: x1 - количество откармливаемых бычков в год; x2 - количество выращиваемых партий быстрорастущих новогодних елей по 1000 шт. каждая в год. 3. Целевая функция: 5000 x1 + 2500 x2  max, где 5000 - чистый доход от одного бычка, руб.; 2500 - чистый доход от одной партии деревьев (1000 шт. по 2,5 руб.). 4. Ограничения: 4.1. По использованию земли, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 x1 + 150 x2  6000 4.3. По трудовым ресурсам, ч: 20 x1 + 20 x2  200 4.4. Обязательства по контракту, шт.: x1  2 4.5. Областные ограничения: x1  0, x2  0

4 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП Отображая на графике прямые, соответствующие следующим уравнениям, 4 x1 + 1,5 x2 = 24 1200 x1 + 150 x2 = 6000 20 x1 + 20 x2 = 200 x1 = 2 x2 = 0 заштриховываем область, в точках которой выполняются все ограничения. Каждая такая точка называется допустимым решением, а множество всех допустимых решений называется допустимой областью. Очевидно, что решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области, которое, в свою очередь, называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, максимизирующее функцию W=5000 x1 + 2500 x2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

5 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП

6 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Графическое решение задачи ЛП Перебор всех угловых точек области допустимых решений приводит к нахождению максимального дохода в размере 34 тыс. руб. (W=5000x1+2500x2), которое лесничество может извлечь, выращивая 3,6 бычка и 6,4 партии новогодних елей. Целочисленные методы (например, перебор) дают x1=3 и x2=6, что приводит к доходу в 30 тыс. руб., x1=4 и x2=5 приводит к более оптимальному результату в 32,5 тыс. руб., точка x1=3 и x2=7 приводит к аналогичному результату. Графический метод ввиду большой размерности реальных практических задач ЛП достаточно редко применяется, однако он позволяет ясно уяснить одно из основных свойств ЛП - если в задаче ЛП существует оптимальное решение, то по крайней мере одна из вершин допустимой области представляет собой оптимальное решение. Несмотря на то, что допустимая область задачи ЛП состоит из бесконечного числа точек, оптимальное решение всегда можно найти путем целенаправленного перебора конечного числа ее вершин. Рассматриваемый далее симплекс-метод решения задачи ЛП основывается на этом фундаментальном свойстве.

7 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Решение задачи ЛП в MS Excel Одной из встроенных функций редактора электронных таблиц MS Excel (необходимо отметить галочку во время установки MS Office) является "Поиск решения". Этот пакет позволяет быстро решать задачи линейного и нелинейного программирования.

8 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Задача ЛП в стандартной форме Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид: W = c1x1 + c2x2 + ... + cnxn  min (max) при ограничениях a11x1 + a12x2 + ... + a1nxn = b1; a21x1 + a22x2 + ... + a2nxn = b2; ... am1x1 + am2x2 + ... + amnxn = bm; x10; x20;...; xn0 b10; b20;...; bm0 В матричной форме W = cx  min (max) при ограничениях Ax = b; x0; b0, где A - матрица размерности m*n, x - вектор-столбец переменных размерности n*1, b - вектор-столбец ресурсов размерности m*1, с - вектор-строка оценок задачи ЛП 1*n.

9 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Преобразование неравенств Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных. Уравнение из предыдущего примера 4x1 + 1,5x2  24 можно преобразовать в равенство при помощи остаточной неотрицательной переменной 4x1 + 1,5x2 + x3 = 24. Переменная x3 неотрицательна и соответствует разности правой и левой частей неравенства. Аналогично x1  2 можно преобразовать путем введения избыточной переменной x4: x1 - x4 = 2.

10 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Преобр-е неогр. по знаку перем-х Преобразование неограниченных по знаку переменных Переменные, принимающие как положительные, так и отрицательные значения, следует заменять разностью двух неотрицательных: x = x+ - x-; x+0; x-  0. Пример. 3x1+4x2+5x3+4x4  max 2x1+x2+3x3+5x4  5 5x1+3x2+x3+2x4  20 4x1+2x2+3x3+x4 = 15 x10; x20; x3 0; x4 =  знак -3x1-4x2+5x3-4x4  min 2x1+x2-3x3+5x4-x5 = 5 5x1+3x2-x3+2x4+x6 = 20 4x1+2x2-3x3+x4 = 15 x10; x20; x30; x4 =  знак; x4 =x8-x7 -3x1-4x2+5x3-4x8+4x7 min 2x1+x2-3x3+5x8-5x7-x5 = 5 5x1+3x2-x3+2x8-2x7+x6 = 20 4x1+2x2-3x3+x8-x7= 15 x1,x2,x3,x5,x6,x7,x80; x4=x8 -3x1-4x2+5x3-4x4+4x7 min 2x1+x2-3x3+5x4-5x7-x5 = 5 5x1+3x2-x3+2x4-2x7+x6 = 20 4x1+2x2-3x3+x4-x7= 15 x1,x2,x3,x4,x5,x6,x70; x8 заменили на x4

11 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Симплекс-метод ЛП Симплекс-метод представляет собой итеративную процедуру решения задач ЛП, записанных в стандартной форме, система уравнений в которой и с помощью элементарных операций над матрицами приведена к каноническому виду: x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. Переменные x1, x2,...,xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (xm+1, ...,xn) называются небазисными переменными. Для приведения системы к каноническому виду можно использовать два типа элементарных операций над строками: Умножение любого уравнения системы на положительное или отрицательное число. Прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

12 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Симплекс-метод ЛП Запись задачи в виде уравнений x1 + a1,m+1xm+1 + ... + a1sxs+...+ a1nxn = b1; x2 + a2,m+1xm+1 + ... + a2sxs+...+ a2nxn = b2; ... xm + am,m+1xm+1 + ... + amsxs+...+ amnxn = bm. тождественна записи в виде матриц 1 0 .. 0 a1,m+1 .. a1s .. a1n x1 b1 0 1 .. 0 a2,m+1 .. a2s .. a2n x2 = b2 . . .. . . .. . .. . .. .. 0 0 .. 1 am,m+1 .. ams .. amn xn bm

13 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 1. Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. xi=0, i=m+1,...,n. Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных неотрицательны, т.е. xj = bj  0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: W=cbxb=c1b1+c2b2+...+cmbm. Заполняем первоначальную таблицу симплекс - метода:

14 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 2. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения сj = сj - cbSj, где сb - вектор оценок базисных переменных; Sj - j-тый столбец из коэффициентов aij в канонической системе, соответствующей рассматриваемому базису. Дополняем первоначальную таблицу c - строкой.

15 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 3. Если все оценки cj  0 (cj  0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено. 4. В противном случае в базис необходимо ввести небазисную переменную xr с наибольшим значением cj вместо одной из базисных переменных (см. таблицу).

16 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Алгоритм симплекс-метода 5. При помощи правила минимального отношения min(bi/air) определяем переменную xp, выводимую из базиса. Если коэффициент air отрицателен, то bi/air=. В результате пересечение столбца, где находится вводимая небазисная переменная xr, и строки, где находится выводимая базисная переменная xp, определит положение ведущего элемента таблицы. 6. Применяем элементарные преобразования для получения нового допускаемого базового решения и новой таблицы. В результате ведущий элемент должен равняться 1, а остальные элементы столбца ведущего элемента принять нулевое значение. 7. Вычисляем новые относительные оценки с использованием правила скалярного преобразования и переходим к шагу 4.

17 слайд

Описание слайда:

Теория принятия решений ПетрГУ, А.П.Мощевикин, 2004 г. Пример реш-я симплекс-методом Пример – Оптимизация размещения побочного производства лесничества 3. Целевая функция: 5000 x1 + 2500 x2  max, 4. Ограничения: 4.1. По использованию земли, га: 4 x1 + 1,5 x2  24 4.2. По бюджету, руб.: 1200 x1 + 150 x2  6000 4.3. По трудовым ресурсам, ч: 20 x1 + 20 x2  200 4.4. Обязательства по контракту, шт.: x1  2 4.5. Областные ограничения: x1  0, x2  0 Приведем задачу к стандартной форме: 4 x1 + 1,5 x2 +x3= 24 1200 x1 + 150 x2 +x4= 6000 20 x1 + 20 x2 +x5= 200 x1 – x6= 2 x1 ... x6  0 Первые три уравнения имеют соответственно по базисной переменной x3, x4, x5, однако в четвертом она отсутствует ввиду того, что при переменной x6 стоит отрицательный единичный коэффициент. Для приведения системы к каноническому виду используем метод искусственных переменных. x1 – x6+x7= 2, ввели искусственную переменную x7.