В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel , нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel » внизу окна:
Далее в открывшемся списке нужно выбрать Надстройки
, затем установить курсор на пункт Поиск решения
, нажать кнопку Перейти
и в следующем окне включить пакет анализа.
Заполните данные
Значение переменных X i может различаться, но целевая функция F(x) должна иметь такое же значение.
Иногда задание звучит следующим образом: расчеты осуществить на ЭВМ, привести распечатку полученных результатов.
MS Excel позволяет представить результаты поиска решения в форме отчета. Существует три типа таких отчетов:
- Результаты (Answer). В отчет включаются исходные и конечные значения целевой и влияющих ячеек, дополнительные сведения об ограничениях.
- Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
- Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.
Пример . В библиотеке работают 6 пожилых уборщиц. Каждая из них по своим физическим возможностям и состоянию здоровья может выполнять только определенные виды работ, причем с определенной производительностью. Площадь каждой из работ известна. Нужно добиться минимума времени на уборку помещений.
ПРОИЗВОДИТЕЛЬНОСТЬ БАБУШЕК м 2 . /мин |
|||||||
| Баба Аня | Белла Петровна | Баба Варя | Баба Галя | Домна Ивановна | Евгения Карловна | Площадь работ | |
| Мытье окон | 2 | 0 | 0 | 1 | 0 | 0 | 46 |
| Мытье полов | 0 | 1 | 0 | 0 | 0 | 0 | 300 |
| Протирка столов | 0 | 0 | 2 | 0 | 0.2 | 1 | 50 |
| Чистка дорожек | 0 | 0 | 0 | 2 | 0 | 4 | 100 |
Пример
.На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указаны общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Найти оптимальное соотношение количества кормов и численности поголовья лис и песцов.
. Алгоритм симплекс-метода
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
Решение:
I итерация:
х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:
Приведем целевую функциюк следующему виду:
На основе полученной задачи сформируем исходную симплекс-таблицу:
Таблица 5.3
Исходная симплекс-таблица
Оценочные отношения |
||||
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
6 этап: проверка оптимальности.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
Таблица 5.4
Исходная симплекс-таблица
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.
9.1. Преобразование разрешающего элемента.
Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:
Полученный результат вписываем в аналогичную клетку таблицы 5.5.
9.2. Преобразование разрешающей строки.
Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.
9.3. Преобразование разрешающей колонки.
Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.
9.4. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:
«х3 »: .
Аналогично преобразуются значения других клеток:
«х3 х1 »: ;
«х4
»: 
;
«х4 х1 »: ;
«х6
»: 
;
«х6 х1 »: ;
«»: 
;
«х1
»: 
.
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
II итерация:
1 этап: составление симплекс-таблицы.
Таблица 5.5
Симплекс-таблица II итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):
Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.6
Симплекс-таблица II итерации
Оценочные отношения |
||||
3/1=3 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.
III итерация
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.7
Симплекс-таблица III итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.8, минимальным является отношение, соответствующее строке «х4 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.8
Симплекс-таблица III итерации
Оценочные отношения |
||||
5/5=1 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.
IV итерация
1 этап: построение новой симплекс-таблицы.
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.9
Симплекс-таблица IV итерации
Оценочные отношения |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.9) нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
7 этап: проверка альтернативности решения.
Найденное решение является единственным, так как в строке целевой функции (таблица 5.9) нет нулевых элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.
Пример 5.2. Решить вышеприведенную задачу линейного программирования при условии, что целевая функция минимизируется:
Решение:
I итерация:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.
Задача 1 (распределительная)
На предприятии 4 вида продукции могут вырабатываться на 3 отдельных взаимозаменяемых машинах.
Известны:
· Производственное задание по выпуску продукции разных видов в планируемом периоде
- · Фонд эффективного рабочего времени оборудования в планируемом периоде - ;
- · Нормы затрат машинного времени на изготовление единицы продукции - ;
- · Прибыль в руб. от реализации единицы продукции, выработанной на том или ином оборудовании - .
Исходная информация отображается в таблице следующей формы.
Таблица 1. Исходные данные
|
Фонд эф. раб. врем. - |
Нормы затрат врем. на ед. продукции - прибыль на ед. продукции - |
||
В задаче требуется найти план распределения производственного задания по выпуску продукции между исполнителями
при котором задание было бы выполнено с максимальной суммарной прибылью от реализации продукции.
РЕШЕНИЕ
Разработка экономико - математической модели.
Искомые переменные - характеризуют объём выпуска й продукции м исполнителем.
Тогда матрица искомых переменных
характеризует план распределения производственного задания по выпуску продукции между исполнителями.
Целевая функция
характеризующая суммарную прибыль от реализации всей продукции, должна быть максимизирована.
Ограничения по наличию и использованию эффективного рабочего времени исполнителей примут вид системы линейных неравенств (2):
Эта система ограничений характеризует условие, что суммарные затраты эффективного рабочего времени каждым исполнителем в планируемом периоде на выпуск всех видов продукции не должны превышать фонда времени. Таким образом, в результате решения задачи каждый исполнитель получит своё задание, исходя из его возможностей. Если в решении задачи какая - то уравновешивающая переменная и примет значение, - она будет характеризовать недоиспользованное эффективное рабочее время у того или иного исполнителя, которое в производственных условиях может быть использовано на выпуск продукции сверх задания.
Следующий блок ограничений должен отражать условие обязательного выполнения общего производственного задания по выпуску продукции по видам и будет представлен системой линейных уравнений (3):
Условие не отрицательности переменных:
Приведём задачу к каноническому виду, для этого в неравенства (2) добавим переменные, а в равенства (3) добавим 4 искусственных базиса. В результате запишем математическую модель задачи в каноническом виде:
Симплекс-метод
Решим данную задачу симплекс - методом, заполнив таблицу. Решение проходит за несколько итераций. Покажем это.
Таблица 1
В самой верхней строке таблицы заносятся коэффициенты целевой функции, вторая строка - это наименование всех неизвестных, входящих в симплексные уравнения. В первый столбец слева записывают коэффициенты, целевой функции, которые соответствуют базисным неизвестным, вошедшим в исходную программу (записанным в столбце). Следующий, третий по счёту, столбец в первой симплексной таблице - заполняется значениями базисных неизвестных. Далее идут столбцы, которые представляют векторы условий. Количество их равно 19. В следующем, первым по счёту после матрицы условий столбце - записываются суммы всех элементов по строкам. В столбце записываются частные от деления элементов итогового столбца В на элементы некоторого столбца, матрицы условий. Так как у нас есть искусственный базис, то в индексной строке будет вести два подсчёта, в первой из них, учитывая переменные, а во втором только искусственный базис. Так как у нас задача максимизации, то необходимо выводить из базиса искусственные базисы. В индексной второй строке выбираем наибольшую положительную оценку. У нас - это первый столбец. Найдём оценочные отношения
и. Из этих отношений выбираем наименьшее, у нас это четвёртая строка, для неё оценочное отношение равно 1300. Выделяем строку. Последний столбец - это коэффициент, на который умножается каждый элемент строки при пересчёте. Он получается делением элементов выделенного столбца на ключевой элемент, который находится на пересечении выделенного столбца и строки, у нас это 1. Пересчёт делаем для всех невыделенных элементов, который осуществляется следующим образом: от пересчитываемого элемента вычитаем элемент ключевой строки, умноженный на пересчитываемый коэффициент строки: и так все элементы. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Последние две строки - индексные строки, где пересчитываются значения целевой функции, а также вся индексная строка, когда все элементы будут положительными или нулевыми - задача будут решена.
Покажем это.
Таблица 2
Выделим столбец с переменной. Находим оценочные отношения, из которых выбираем наименьшее - это 550. Из базиса выводим искусственную переменную, при этом в базис вводим переменную. Когда выводится искусственный базис из базиса, соответствующий столбец убираем.
Таблица 3
Выделим столбец. Наименьшее оценочное отношение 600, находится в шестой строке. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Таблица 4
Выделим столбец с переменной. Наименьшее оценочное отношение 28,57, находится в первой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 5
Выделим столбец с переменной. Наименьшее оценочное отношение 407,7, находится в третьей строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 6
Выделим столбец с переменной. Наименьшее оценочное отношение 344,3, находится в седьмой строке. Из базиса выводим искусственный базис, при этом в базис вводим переменную.
Таблица 7
Выделим столбец с переменной. Наименьшее оценочное отношение 3,273, находится во второй строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 8
Выделим столбец с переменной. Наименьшее оценочное отношение 465, находится в седьмой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 9
Выделим столбец с переменной. Наименьшее оценочное отношение 109, находится в третьей строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 10
Выделим столбец с переменной. Наименьшее оценочное отношение 10, находится в первой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 11
Выделим столбец с переменной. Наименьшее оценочное отношение 147, находится во второй строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 12
Выделим столбец с переменной. Наименьшее оценочное отношение 367, находится в пятой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 13
Выделим столбец с переменной. Наименьшее оценочное отношение 128, находится в четвёртой строке. Из базиса выводим переменную, при этом в базис вводим переменную.
Таблица 14
Так как в индексной строке нет отрицательных оценок, получен оптимальный план, при котором объём выпуска продукции представлен матрицей
при этом прибыль максимальная и составляет 17275,31 руб.
Решение задачи с помощью Excel
Математическую модель задачи необходимо перенести в ЭТ EXCEL. Для этого:
- · Продумать организацию исходных данных модели (коэффициенты целевой функции и ограничения), снабдив понятными названиями.
- · Зарезервировать в отдельных ячейках независимые переменные математической модели.
- · В одной из ячеек создать формулу, определяющую целевую функцию.
- · Выбрать ячейки и поместить в них формулы, соответствующие левым частям ограничений.
- · Войти в пункт меню "Поиск решения", ввести необходимые данные и получить оптимальное решение задачи.
- · Проанализировать полученное решение и отчёты.
Рассмотрим последовательность действий по реализации этих этапов решения задачи с помощью EXCEL.
Создадим таблицу для ввода исходных данных.
В созданную форму введём исходные данные.
Коэффициенты целевой функции, выражающие прибыль, от производства единицы продукции каждого вида (единичная прибыль), записаны в ячейки В6:M6.
Коэффициенты ресурсных ограничений, определяющие потребность в каждом из видов ресурсов для производства единицы продукции, размещены в ячейках В9:M15. В ячейках P9:P15 записаны правые части ограничений на ресурсы. Для независимых переменных задачи - искомых объёмов производства продукции зарезервированы ячейки В3:M3.
В ячейку N7 вводим формулу для целевой функции, применив команду вставки функции СУММПРОИЗВ:
А также заполняем ограничения правой части.
После этого можно приступать к поиску решения. Для решения оптимизационных задач в EXCEL используется команда ПОИСК РЕШЕНИЯ меню СЕРВИС.
Эта команда оперирует с тремя основными компонентами построенной в ЭТ оптимизируемой модели:
- · Ячейкой, содержащей целевую функцию задачи.
- · Изменяемыми ячейками, содержащими независимые переменные.
- · Ячейками, содержащими левые части ограничений на имеющиеся ресурсы, а также простые ограничения на независимые переменные.
Рассмотрим последовательность ввода этих компонентов.
Курсор в ячейку N7 и команда СЕРВИС - Поиск решения. На экране появится диалоговое окно.
В окне заполняем поле Установить целевую ячейку, в котором должен стоять адрес $N$7. Далее устанавливаем кнопку на поиск максимального значения. В поле Изменяя ячейки введём адреса искомых переменных $B3:$M3. Затем следует ввести ограничения, путём кнопки Добавить.
Теперь, когда все ограничения для поиска оптимального решения заданы можем нажать кнопку:
После этого получим решение задачи.
Если вычисления оказались успешными, после завершения поиска решения значения будут вставлены в таблицу, а также можно указать Тип отчёта - Результаты, в результате которого можем получить следующий отчёт. рабочий время оборудование прибыль
Следовательно, решение в EXCEL такое же, как и при СИМПЛЕКС методе, а это значит, что рассматриваемая задача, решена, верно.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
 |
Правая часть ограничений системы уравнений имеет вид:
Запишем текущий опорный план:
 |
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x
при 
. min
(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x
3 . Сделаем исключение Гаусса для столбца x
2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x
1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x
4 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными 
нет отрицательных элементов.
Решение можно записать так: 
.
Значение целевой функции в данной точке: F
(X
)=
.
Пример 2. Найти максимум функции
Р е ш е н и е.
Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x
2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
 |
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 1. Из базиса выходит вектор x
2 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x
3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор x
5 . Сделаем исключение Гаусса для столбца x
3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
Пример 2. Найти оптимальный план задачи линейного программирования:
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
1. Преобразовываем неравенства в равенства
2. Находим начальное допустимое базисное решение
3. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, то процесс закончен.
4. На основе условия допустимости выбираем исключаемая переменная
5. Вычисляем элементы новой ведущей строки
новая ведущая строка = текущая строка/ведущий элемент
6. Вычисляем элементы остальных строк, включая z-строку
новая строка = текущая строка – ее коэффициенты в ведущем столбце * новую ведущую строку
Переходим к шагу 3.
Для удобства записи итерационного процесса все значения записываем в Симплекс-таблицу.
2. Пример решения задачи лп с использованием пакета ms excel
Для многих задач оптимизации удобно применять модель линейного программирования. Суть задачи заключается в составлении системы неравенств, описывающих соответствующие ограничения задачи и задания функции оптимизации.
Для нахождения решения в подобных моделях, можно использовать средство MS EXCEL – ПОИСК РЕШЕНИЯ.
Рассмотрим, как составить модель линейного программирования и найти ее решение на примере.
2.1. Постановка задачи
На трех станках обрабатываются детали двух видов (А и Б), причем каждая деталь проходит обработку на всех станках. Известно время обработки деталей на каждом станке, время работы станков в течение одного цикла производства и прибыль от продажи одной детали каждого вида (данные в таблице). Составить план производства, обеспечивающий наибольшую прибыль.
2.2. Построение математической модели
Обозначим через х 1 и х 2 количество единиц деталей видов А и Б, планируемое к выпуску. Тогда время обработки х 1 деталей вида А на первом станке составляет 1* х 1 ; х 2 деталей вида Б соответственно 2*х 2 . Суммарное время работы станка I для изготовления планируемого количества деталей равно х 1 +2*х 2 , оно ограничено 16 часами работы этого станка в течение одного цикла производства. Поэтому должно выполняться неравенство:
х 1 +2*х 2 <=16;
Аналогично для станков II и III получаем неравенства соответственно:
х 1 + х 2 <=10;
3*х 1 + х 2 <=24;
Кроме того, по смыслу определения веденных величин х 1 и х 2 , должны выполняться условия: х 1 >=0; х 2 >=0;
Таким образом, получаем систему неравенств, называемую системой ограничений задачи:
Любое решение (х 1 ; х 2) системы ограничений называется планом выпуска продукции или допустимым планом задачи.
Прибыль от реализации х 1 единиц деталей вида А равна 4 . х 1 , а прибыль от реализации х 2 единиц деталей вида Б равна 2х 2. Суммарная прибыль от реализации продукции, выпущенной согласно плану (х 1 ; х 2) равна:
F (х 1 ; х 2 )=4х 1 +2х 2 (тыс. руб).
Линейная функция F (х 1 ; х 2 ) называется целевой функцией задачи.
По условию задачи требуется найти такой план (х 1 ; х 2) при котором прибыль была бы максимальной.
Таким образом, построена математическая модель задачи как задачи линейного программирования:
F (х 1 ; х 2 )=4х 1 +2х 2 → max
