Н.А. Курганова
ОСНОВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Н.А. Курганова
ОСНОВНЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
Учебное пособие
Омск 2011
Печатается по решению научно-методического совета Омского государственного педагогического университета
Н.А. Курганова. Основные методы решения задач линейного программирования: Учебное пособие. – Омск, 2011. – , с.
Учебное пособие составлено с учетом современных требований к подготовке студентов, обучающихся по специальностям «Информатика», «Математика», «Математические методы в экономике». Материалы, представленные в пособии, являются базовыми для изучения учебных курсов «Исследование операций и методы оптимизации», «Математические методы в экономике» и др.
В работе представлен основной теоретический материал, необходимый для практического решения задач оптимизации, подкрепленный разобранными примерами решения задач на основе использования различных математических приложений. Пособие содержит задания для самостоятельного выполнения, а также лабораторный практикум.
© Курганова Н.А., 2011 г.
Содержание
Введение. 5
Тема 1. Постановка задачи линейного программирования. Геометрический метод решения задач линейного программирования. Основные понятия, теоремы, следствия. 6
1.1. Постановка задачи линейного программирования. 6
1.2. Геометрический метод решения задач ЛП.. 9
Теоретические вопросы.. 11
Лабораторная работа №1. Геометрическое решение задачи ЛП при помощи математического пакета MathCad 12
Лабораторная работа №2. Геометрическое решение задачи ЛП при помощи математического пакета Maple 17
Задания для самостоятельной работы.. 26
Лабораторная работа №3. Решение оптимизационных задач в системах MathCad, Maple, Excel, в специализированном пакете SimplexWin. 29
Задания для самостоятельной работы.. 42
Тема 2. Симплекс-метод. 44
2.1. Табличный симплекс-метод (в чистом виде) 45
2.2. Табличный симплекс метод. Метод искусственного базиса (М-метод) 49
Теоретические вопросы.. 50
Лабораторная работа №4. Реализация пошагового алгоритма решения задачи линейного программирования табличным симплекс-методом средствами Excel при выполнении всех условий 51
Лабораторная работа №5. Реализация пошагового алгоритма решения задачи линейного программирование методом искусственного базиса (М-методом) средствами Excel 61
Задания для самостоятельной работы.. 66
Приложение 1. 69
Приложение 2. 70
Библиографический список. 71
Введение
Учитывая возрастающие требования к высшему образованию в целом и к экономическому в частности, необходимо повышать общую математическую грамотность будущих специалистов. При этом необходимо, чтобы математические методы были рассмотрены в качестве приложений к экономической науке.
Рассмотренные в пособии методы позволяют разрешать ряд определенных экономических ситуаций, с учетом того, что математическая модель каждой ситуации представляет собой задачу линейного программирования. Математическая модель отражает проблему в абстрактной форме и позволяет учитывать характеристики, от которых зависит эта проблема.
Приведенные в пособии темы охватывают такие методы решения задач линейного программирования, как геометрический метод и симплекс-метод. Эти методы могут рассматриваться при изучении таких дисциплин, как «Исследование операций и методы оптимизации», «Методы оптимизации», «Экономико-математические методы и модели».
Исследование экономических проблем, возникающих перед специалистами, требует привлечения не только средств математического моделирования, но и использования современных информационных компьютерных технологий. В связи с этим в пособии в качестве компьютерной поддержки каждого метода применяются табличный процессор Excel, математические пакеты (Mathcad, Maple), а также специализированный пакет SimplexWin.
В каждом теме дается обзор основных теоретических понятий, общих алгоритмов применения методов оптимизации для решения задач линейного программирования, перед каждой лабораторной работой представлен список теоретических вопросов, при помощи которых можно осуществить самоконтроль. Каждая лабораторная работа позволяет познакомиться с основными методами решения задач линейного программирования на конкретно разобранном примере. После выполнения лабораторной работы предусмотрены задания для самостоятельной работы, что позволяет отработать навыки по составлению экономико-математических моделей и методов их решения.
Тема 1. Постановка задачи линейного программирования. Геометрический метод решения задач линейного программирования. Основные понятия, теоремы, следствия.
I. Оформление исходных данных.
1. Откройте математический пакет MathCad и введите заголовок Геометрический метод решения задач линейного программирования, выбрав команду Insert–Text Region.
2. Наберите целевую функцию, систему ограничений и условие неотрицательности переменных в текстовом процессоре (Word), используя редактор формул, а затем скопируйте «текст» задания на рабочий лист в пакете MathCad.
I. Оформление заголовка.
1. Запустите программу Maple и введите заголовок Геометрический метод решения задачи ЛП, используя команду Insert – Text.
Задачи о пищевом рационе
Задача 1. Стоимость 1 единицы продукта P1 – 2 денежные единицы, продукта P2 – 3 денежные единицы. Требуется так организовать питание, чтобы стоимость его была наименьшей.
| Питательные вещества | Минимальная норма | Содержание питательного вещества в единице продукта | |
| Р1 | Р2 | ||
| белки | |||
| жиры | |||
| углеводы | |||
| Прибыль |
Задача 2.Требуется составить суточный рацион для откорма свиней минимальной себестоимости, причем в рацион должно быть включено не более 2.5 кг ячменя. Минимально потребление кормовых единиц в сутки 2.4 кг, протеина 200 г. Исходные данные приведены в таблице:
| Вид корма | Цена | Содержание питательных веществ | |
| кормовые единицы | протеин | ||
| комбикорм | 1 кг | 100 г | |
| ячмень | 1.2 кг | 80 г |
I. Оформление исходных данных.
1. Запустите программу MathCad и введите заголовок Нахождение максимального значения функции.
2. Введите функцию 
.
3. Присвойте начальные значения переменным:
.
I. Оформление исходных данных.
1. Запустите программу Maple и введите заголовок Нахождение максимального значения функции, используя команду Insert – Text.
2. Подключите библиотеку simplex, предназначенную для оптимизации линейных систем с использованием симплексного алгоритма.
> with(simplex):
Warning, the protected names maximize and minimize have been redefined and unprotected
3. Задайте целевую функцию и систему ограничений.
> f:=x1+2*x2;
> syst_ogr:={-3*x1+14*x2<=1, x1+x2<=6, x1-x2>=3, x1+4*x2>=4};
II. Нахождение оптимального плана и оптимального значения целевой функции.
1. Для нахождения максимума целевой функции используйте функцию maximize, формат которой следующий maximize(<функция>, <система ограничений>, <опции>);
При этом условие неотрицательности переменных удобно указать опцией NONNEGATIVE.
> optimum:=maximize(f,syst_ogr,NONNEGATIVE);
2. Используйте команду subs, которая позволяет подставить значения переменных x1 и x2 в функцию f.
> fmax:=subs(x1=83/17,x2=19/17,f);
3. Примените функцию evalf для представления ответа в форме действительного числа с 4 значащими цифрами.
> fmax:=evalf(fmax,4);
Ознакомиться с вариантом решения задачи ЛП без пояснений можно в приложении.
Решение оптимизационных задач в специализированном пакете SimplexWin. http://www.simplexwin.narod.ru/
Данная программа предназначена для решения задач линейного программирования симплекс методом.
Задача. Найти значения переменных x1и x2, при которых 
при ограничениях
Порядок выполнения работы:
I. Оформление исходных данных.
1. Запустите программу SimplexWin и установите требуемый размер матрицы ограничений, выбрав в меню команду Настройки – Размер матрицы (рис. 13).
Рис. 13. Определение размера матрицы.
2. Введите данные (рис. 14). Если задача вводится не в канонической форме, то дополнительные переменные и искусственные базисы (а также соответствующие им коэффициенты целевой функции) добавляются автоматически.
Рис.14. Ввод данных.
II. Нахождение оптимального плана и оптимального значения целевой функции.
1.
 |
Нажмите кнопку Вычислить и получите форму Результаты (рис. 15).
Рис. 15. Форма Результаты.
2. В форме Результаты нажмите кнопку Результат, которая позволяет произвести решение задачи в автоматическом режиме и отобразить на экране последнюю симплексную таблицу и результат (рис. 16).
Рис. 16. Решение задачи.
Решение оптимизационных задач в Excel[1]
Рассмотрим пример нахождения для следующей задачи линейного программирования.
Задача. Найти значения переменных x1и x2, при которых 
при ограничениях
Порядок выполнения работы:
I. Оформление исходных данных.
1. Создайте экранную форму для ввода условий задачи (переменных, целевой функции, ограничений) и введите в нее исходные данные (коэффициенты целевой функции, коэффициенты при переменных в ограничениях, правые части ограничений) (рис. 17).
Рис. 17. Экранная форма задачи (курсор в ячейке D6).
Замечание: В экранной форме на рис. 17 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка в Excel. Так, например, переменным задачи соответствуют ячейки B3 ( 
), C3 ( 
), коэффициентам целевой функции соответствуют ячейки B6 ( 
), C6 ( 
), правым частям ограничений соответствуют ячейки F10 ( 
), F11 ( 
),F12 ( 
) и т.д.
2. Введите зависимости из математической модели в экранную форму, т.е. введите формулу для расчета целевой функции и формулу для расчета значений левых частей ограничений.
Согласно условию задачи значение целевой функции определяется выражением 
. Используя обозначения соответствующих ячеек в Excel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B6, C6).
Для того чтобы задать формулу зависимости для целевой функции проделайте следующее:
– поставьте курсор в ячейку D6;
– вызовите окно Мастер функций – шаг 1 из 2, нажав кнопку 
на стандартной панели инструментов;
– выберите в окне Категориякатегорию Математические;
– в окне Функциявыберите функцию СУММПРОИЗВ;
– в появившемся окнеСУММПРОИЗВ в строку Массив 1введите выражение B$3:C$3, а в строку Массив 2 – выражение B6:С6;
– нажмите кнопку OK.
Рис. 18. Ввод формулы для расчета ЦФ в окне Мастер функций.
После ввода ячеек в строки Массив 1 и Массив 2в окне СУММПРОИЗВ появятся числовые значения введенных массивов (рис. 18), а в экранной форме появится текущее значение, вычисленное по введенной формуле, то есть 0 (так как в момент ввода формулы значения переменных задачи нулевые) (рис. 19).
Замечание: Символ $ перед номером строки означает, что при копировании этой формулы в другие места листа Excel номер строки 3 не изменится. Символ :означает, что в формуле использованы все ячейки, расположенные между ячейками, указанными слева и справа от двоеточия.
Левые части ограничений задачи представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи (B3, C3), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения (B10, C10 – 1 ограничение; B11, C11 – 2 ограничение; B12, C12 – 3 ограничение).
Формулы, задающие левые части ограничений задачи, отличаются друг от друга и от формулы в целевой ячейке D6только номером строки во втором массиве. Этот номер определяется той строкой, в которой ограничение записано в экранной форме. Поэтому для задания зависимостей для левых частей ограничении достаточно скопировать формулу из целевой ячейки в ячейки левых частей ограничений.
Для расчета значений левых частей ограничений выполните следующее:
– поставьте курсор в ячейку D6 и скопируйте в буфер содержимое ячейки (клавишами Ctrl+C);
– поставьте курсор поочередно в поля левой части каждого из ограничений, то есть D10,D11, D12, и вставляйте в эти поля содержимое буфера (клавишами Ctrl+V) (при этом номер ячеек во втором массиве формулы будет меняться на номер той строки, в которую была произведена вставка из буфера).
После ввода на экране в полях D10,D11, D12появится 0 (нулевое значение) (рис. 19).
Рис. 19. Экранная форма задачи после вода
всех необходимых формул.
3. Проверьте правильность введения формул.
Для этого:
– произведите поочередно двойное нажатие левой клавиши мыши на ячейки с формулами, при этом на экране рамкой будут выделяться ячейки, используемые в формуле (рис. 20 и рис. 21).
Рис. 20. Проверка правильности введения
формулы в целевую ячейку D6.
Рис. 20. Проверка правильности введения
формулы в ячейку D10 для левой части ограничений.
4. Задайте целевую функцию и введите ограничения в окне Поиск решения(рис. 21).
Для этого:
– поставьте курсор в ячейку D6;
– вызовите окно Поиск решения, выбрав на панели инструментов Данные – Поиск решения;
– поставьте курсор в поле Установить целевую ячейку;
– введите адрес целевой ячейки $D$6или сделайте одно нажатие левой клавишей мыши на целевую ячейку в экранной форме, что будет равносильно вводу адреса с клавиатуры;
– укажите направление оптимизации целевой функции, щелкнув один раз левой клавишей мыши по селекторной кнопке максимальному значению;
– в окне Поиск решенийв поле Изменяя ячейкивведите ячейки со значениями переменных $B$3:$C$3, выделив их в экранной форме, удерживая левую кнопку мыши;
Рис. 21. Окно Поиск решения.
– нажмите кнопку Добавить;
– в полеСсылка на ячейкувведите адрес ячейки левой части конкретного ограничения, например, $D$10;
– в соответствии с условием задачи выберите в поле знака необходимый знак, например, для 1 ограничения это знак 
;
– в поле Ограничениевведите адрес ячейки правой части, рассматриваемого ограничения, например $F$10;
– аналогичным образом установите соотношения между правыми и левыми частями других ограничений ($D$11 $F$11, $D$12 
$F$12);
– подтвердите ввод всех перечисленных условий нажатием кнопки OK(рис. 22 и рис. 23).
Рис. 22. Добавления условия.
Замечание: Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений, то это можно сделать на жав на кнопки Изменитьили Удалить.
II. Нахождение оптимального плана и оптимального значения целевой функции.
1. Установите параметры решения задачи (рис. 23).
Для этого:
– нажмите кнопку Параметры;
– заполните некоторые поля окна Параметры поиска решения;
– подтвердите установленные параметры нажатием кнопки OK.
Рис. 23. Параметры поиска решения,
подходящие для большинства задач.
Замечание:
Параметр Максимальное времяслужит для назначения времени (в секундах), выделяемого на решение задачи.
Параметр Предельное число итерацийслужит для управления временем решения задачи путем ограничения числа промежуточных вычислений.
Параметр Относительная погрешностьслужит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличивает время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр Допустимое отклонениеслужит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большого допуска поиск решения заканчивается быстрее.
Параметр Сходимостьприменяется только при решении нелинейных задач.
Установка флажка Линейная модельобеспечивает ускорение поиска решения линейной задачи за счет применения симплекс-метода.
Установка флажка Неотрицательные значенияпозволяет ограничить условия для допустимых значений переменных.
Запустите задачу на решение.
2. Запустите задачу на решение.
Для этого:
– нажмите кнопку Выполнить(рис. 24);
Рис. 24. Сообщение об успешном решении задачи
Замечание:
После запуска на решение задачи ЛП на экране появляется окно Результаты поиска решения с одним из сообщений, следующих сообщений:
1. Решение найдено. Все ограничения и условия оптимально выполнены. Сообщение об успешном решении задачи.
2. Поиск не может найти подходящего решения. Сообщение при несовместной системе ограничений задачи.
3. Значения целевой ячейки не сходятся. Сообщение при несовместной системе ограничений задачи.
В окне Результаты поиска решения представлены названия трех типов отчетов: Результаты, Устойчивость, Пределы. Они необходимы при анализе полученного решения на чувствительность.
– нажмите кнопку OK, в экранной форме появится оптимальное решение задачи (рис. 25).
Рис. 25. Экранная форма задачи после получения решения.
Задания для самостоятельной работы
1. Составьте для нижеприведенных текстовых задач экономико-математическую модель.
2. Решите каждую задачу в MathCad, Maple, Excel, специализированном пакете SimplexWin, используя материалы лабораторной работы №3.
3. Сравните полученные ответы.
Задача 1. Бройлерное хозяйство птицеводческой фермы насчитывает 20000 цыплят, которые выращиваются до 8-недельного возраста и, после соответствующей обработки, поступают в продажу. Хотя недельный расход корма для цыплят зависит от их возраста, в дальнейшем будем считать, что в среднем (за 8 недель) он составляет 1 у.е. Для того чтобы цыплята достигли к восьмой неделе необходимых весовых кондиций, кормовой рацион должен удовлетворять определенным требованиям по питательности. Этим требованиям могут соответствовать смеси различных видов кормов, или ингредиентов. В качестве ингредиентов рассмотрим три: известняк, зерно и соевые бобы. Требования к питательности рациона сформулируем, учитывая три вида питательных веществ: кальций, белок и клетчатку. В таблице приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из ингредиентов и удельную стоимость каждого ингредиента. Заметим, что известняк не содержит ни белка, ни клетчатки.
| Ингредиент | Содержание питательных веществ, у.е./кг ингредиента | Стоимость, у.е./кг | ||
| кальций | белок | клетчатка | ||
| известняк | 0,38 | – | – | 0,04 |
| зерно | 0,001 | 0,09 | 0,02 | 0,15 |
| соевые бобы | 0,002 | 0,5 | 0,08 | 0,4 |
Смесь должна содержать: не менее 0,8%, но не более 1,2% кальция; не менее 22% белка; не более 5% клетчатки.
Требуется определить для птицеводческой фермы количество (в кг) каждого из трех ингредиентов, образующих смесь минимальной стоимости при соблюдении требований к общему расходу кормовой смеси и ее питательности.
Задача 2. Предприятие выпускает панели для пультов управления двух видов: стандартные (для работы в обычных условиях) и специального исполнения (для работы при повышенных температурах). При изготовлении панелей используется пластмасса и алюминий. Для изготовления одной стандартной панели требуется 12,5 кг пластмассы и 8 кг алюминия; для изготовления одной панели специального исполнения – 7,2 кг пластмассы и 14,5 кг алюминия. Предприятие имеет 300 кг пластмассы и 400 кг алюминия. Прибыль предприятия от выпуска одной стандартной панели составляет 7 ден. ед., прибыль от выпуска одной панели специального исполнения – 9 ден. ед. Требуется определить, сколько панелей каждого вида должно выпускать предприятие, чтобы получить максимальную прибыль.
Руководство к выполнению заданий для самостоятельной работы.
Для нахождения минимального значения целевой функции в системах MathCad и Maple воспользуйтесь функцией minimize, а в программах Excel и SimplexWin не забудьте переключить направление оптимизации
Тема 2. Симплекс-метод.
В предыдущей теме мы рассмотрели такой метод решения задач линейного программирования, как геометрический. Геометрический метод имеет ряд недостатков, к которым можно отнести неточность ручных построений и наличие двух переменных.
В лабораторных работах №1 и №2 мы показали каким образом возможно устранить неточность ручных построений. Применение же симплекс-метода позволит решать задачи линейного программирования любой размерности, т.е. с любым количеством переменных.
Симплекс-метод – это метод целенаправленного перебора опорных планов задачи линейного программирования в направлении улучшения значения целевой функции.
Он позволяет на конечное число шагов расчета либо найти оптимальное решение, либо установить, что оптимального решения не существует[4].
Отметим, что решение задач линейного программирования на основе симплекс-метода состоит в целенаправленном переборе угловых точек. Минимум или максимум целевой функции всегда достигается при значениях переменных 
, 
,…, 
, соответствующих одной из угловых точек ОДР. Другими сло-
вами, оптимальное решение всегда находится в угловой точке ОДР. [11]
II. Оформление исходных данных.
1. Откройте табличный процессор Excel и введите заголовок Табличный способ решения задач линейного программирования.
2. Заполните начальную симплекс-таблицу.
Шапка таблицы: столбец базисных переменных (B), столбец свободных членов, имеющиеся переменные.
Следующая строка таблицы соответствует первому ограничению. Базисная переменная, найденная в первом ограничении, свободный член, коэффициенты при переменных соответствующего ограничения. Аналогичным образом заполняются 2 и 3 строки.
Последняя строка – это строка целевой функции, которая заполняется следующим образом, свободный член без изменения знака, а коэффициенты при переменных с противоположным (рис. 26).
Рис. 26. Исходная симплекс таблица.
5. Проконтролируйте правильность заполнения таблицы. Так как 
, 
, 
- базисные переменные, то на пересечении (5 строка) с (столбец D) должна стоять 1 (ячейка D5), а в соответствующем столбце ниже – нули, на пересечении (6 строка) с (столбец E) должна стоять 1 (ячейка E6), а в соответствующем столбце ниже – нули, (7 строка) с (столбец H) должна стоять 1 (ячейка H7), а в соответствующем столбце ниже – нули.
3. Запишите значение целевой функции, начальный опорный план, опираясь на столбец свободных членов (рис. 27).
Рис. 27. Значение целевой функции и начальный опорный план.
III. Нахождение оптимального плана и оптимального значения целевой функции.
1. Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным. Организуйте процесс улучшения плана, выполнив предложенные шаги.
2. Среди отрицательных элементов индексной строки выберите наибольший по модулю элемент. Соответствующий столбец назовите ведущим. Данный столбец показывает, какую переменную необходимо включить в базис (рис. 28).
Рис. 28. Выбор ведущего столбца.
3. Теперь необходимо определить какую переменную исключить из базиса. Для этого составьте отношения для всех элементов столбца свободных членов ( 
) к соответствующим элементам ведущего столбца ( 
). Например, в ячейку I5 введите формулу =B5/C5. Растяните формулы для ячеек I6, I7, исключая ячейку индексной строки (рис. 29).
Рис. 29. Составление отношений.
4. Определите результат отношений (таблица 5), учитывая, что в результате может получиться число, отличное от нуля, 0 или бесконечность (рис. 30).
Рис. 30. Результат отношений.
5. Выберите наименьшее из отношений. Строку, в которой получился наименьший результат, назовите ведущей (рис. 31). Данная строка показывает, какую переменную необходимо исключить из базиса.
Рис. 31. Выбор ведущей строки.
6. На пересечении ведущей строки и ведущего столбца получается ведущий элемент (рис. 32).
Рис. 32. Ведущий элемент.
7. Постройте новую симплексную таблицу. Выведите переменную из базиса, на ее место запишите ту переменную, которой соответствует ведущий столбец (рис. 33). В нашем случае – это переменная .
Рис. 33. Новый базис.
8. Так как теперь - базисная переменная, то на пересечении (13 строка) с (столбец C) должна стоять 1 (ячейка С13), а в соответствующем столбце ниже – нули. С помощью элементарных преобразований сделайте ведущий столбец базисным.
Для получения 1 в ячейке С13 необходимо каждый элемент ведущей строки поделить на ведущий элемент.
В ячейку С13 запишите формулу = С5/2 (рис 34), нажмите Enter.
Рис. 34. Получение 1 в ячейке С13.
Растяните формулу (рис. 35).
Рис. 35. Первая строка второй симплексной таблицы.
Затем получите нуль в ячейке С14.
Для этого во второй симплексной таблице 1 (ячейка С13) умножьте на элемент предыдущей таблицы, соответствующий элементу ячейки С14, взятый с противоположным знаком и сложите с этим же элементом.
Так как элемент, соответствующий элементу ячейки С14 равен 1 (ячейка С6), то это означает, что все элементы первой строки второй симплексной таблицы умножаются на (-1) и складывается с соответствующими элементами первой симплексной ьаблицы. Запишите в ячейку С14 формулу =C13*(-1)+C6 (рис. 36).
Рис. 36. Элемент С14 второй симплексной таблицы.
Аналогичным образом получите остальные элементы базисного столбца (рис. 37 и рис. 38).
Рис. 37. Элемент С15 второй симплексной таблицы.
Рис. 38. Элемент С16 второй симплексной таблицы.
9. Растяните формулы базисного столбца по строкам, получите вторую симплексную таблицу (рис. 39).
Рис. 39. Первая и вторая симплексные таблицы.
10. Так в индексной строке есть отрицательные коэффициенты при переменных, то опорный план не является оптимальным.
11. Запишите значение целевой функции, найденный новый опорный план, опираясь на столбец свободных членов (рис. 40). Проконтролируйте, что значение целевой функции максимизируется.
Рис. 40. Значение целевой функции и опорного плана второй симплексной таблицы.
12. Организуйте процесс улучшения плана, выполнив предложенные шаги, начиная с пункта 5, до тех пор пока не будет выполняться какой-нибудь из критериев остановки. Получите третью симплексную таблицу (рис. 41).
Рис. 41. Первая, вторая и третья симплексные таблицы.
13. В индексной строке нет отрицательных элементов, поэтому план 
оптимален, 
.
Задание. Воспользуйтесь материалами лабораторной работы №3. Выполните проверку, используя программу MathCad.
II. Оформление исходных данных.
1. Откройте табличный процессор Excel и введите заголовок Метод искусственного базиса.
2. Заполните начальную симплекс-таблицу, таким же образом как в лабораторной работе №4, добавив в нее столбец для переменной 
и 
-строку (рис. 42).
Рис. 42. Исходная симплекс таблица.
11. Проконтролируйте правильность заполнения таблицы. Так как 
, 
, - базисные переменные, то на пересечении (5 строка) с (столбец F) должна стоять 1 (ячейка F5), а в соответствующем столбце ниже – нули, на пересечении (6 строка) с (столбец G) должна стоять 1 (ячейка G6), а в соответствующем столбце ниже – нули, (7 строка) с (столбец I) должна стоять 1 (ячейка I7), а в соответствующем столбце ниже – нули.
3. Запишите значение целевой функции, начальный опорный план, опираясь на столбец свободных членов (рис. 43).
Рис. 43. Значение целевой функции и начальный опорный план.
III. Нахождение оптимального плана и оптимального значения целевой функции.
1. Так в индексной строке есть отрицательный коэффициент при переменной, то опорный план не является оптимальным. Организуйте процесс улучшения плана, выполнив предложенные шаги.
2. В индексной строке найдите отрицательные элементы. Составьте выражения, учитывая -строку. Получите 
.
В данном случае один отрицательный элемент – это выражение , которое соответствует переменной 
.
3. Соответствующий столбец назовите ведущим. Данный столбец показывает, какую переменную необходимо включить в базис (рис. 44).
Рис. 44. Ведущий столбец.
4. Определите какую переменную необходимо исключить из базиса. Для этого составьте отношения для всех элементов столбца свободных членов ( 
) к соответствующим элементам ведущего столбца ( 
). Найдите ведущую строку и ведущий элемент (рис. 45).
Рис. 45. Ведущая строка и ведущий столбец.
5. Постройте новую симплексную таблицу. Выведите переменную 
из базиса, на ее место запишите ту переменную, которой соответствует ведущий столбец. Выполните симплексные преобразования, таким же образом, как и в лабораторной №4, получите базисный столбец, который соответствует переменной . Значения столбца можно удалить, так как переменная вышла из базиса (рис. 46).
Рис. 46. Первая и вторая симплексные таблицы.
6. Так как в -строке все нули, то ее можно удалить из таблицы и по
Дата: 2016-10-02, просмотров: 220.
