Программирование линейных уравнений по информатике

Программирование решения уравнений

Программирование решения уравнений. Презентация, проект и программный продукт (программа в Pascal)

Скачать:

Предварительный просмотр:

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

Программирование линейных уравнений Работа ученика 9б класса Ф.И.О. обучающегося: Смолькова Андрея Владимировича Руководитель проекта Ф.И.О. Борисова О.А.

Языки программирования — это формальные языки, предназначенные для записи алгоритмов, исполнителем которых будет компьютер. Записи алгоритмов на языках программирования называются программами . Язык Паскаль – универсальный язык программирования. Никлаус Вирт ( 1934 года рождения) — швейцарский учёный, специалист в области информатики, один из известнейших теоретиков в области разработки языков программирования, профессор информатики (компьютерных наук). Разработчик языка Паскаль и ряда других языков программирования.

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

Метод Ньютона , алгоритм Ньютона (также известный как метод касательных ) — это итерационный численный метод нахождения корня заданной функции. Дана непрерывная функция f ( x ), которая содержит единственный корень на отрезке [ a,b ], где b > a при чем определены непрерывны и сохраняют знак f `( x ) f «( x ). Точность е. Выбираем грубое приближение корня х 0 . Найдем значение функции точке х 0 и проведем касательную до пересечения с осью абсцисс, получим значение х 1 . Определим значение функции в точке х 1 , через эту точку проводим касательную и получаем точку х 2 . Повторим этот процесс n раз. Метод Ньютона

Практически перед каждым программистом рано или поздно встает задача определения корней уравнения. На сегодняшний день существует достаточно много алгоритмов решения данной задачи. Все они могут быть разделены на два этапа: отделения и уточнения корней. Первую часть легко выполнить графическим методом. Для выполнения второго этапа решения уравнения можно воспользоваться одним из многих методов уточнения корней уравнения. Заключение

Предварительный просмотр:

Предварительный просмотр:

Муниципальное бюджетное общеобразовательное учреждение

«Гимназия №7» г. Торжка

Программирование решения уравнений

Работа ученика 9Б класса

Смольков Андрей Владимирович

Ф.И.О. Борисова Ольга Александровна

Работа допущена к защите «_____» _______________ 2018г.

Подпись руководителя проекта _________________(__________________)

Паспорт проекта

Название проекта
Программирование решения уравнений

Руководитель проекта
Борисова Ольга Александровна

Автор проекта
Смольков Андрей Владимирович

Учебная дисциплина
Информатика

Тип проекта
Исследовательский

Цель работы
Изучить программную среду PascalABC для решения уравнений

1. Написать программу решения:

1. Системы линейных алгебраических уравнений методом Гаусса
2. Нелинейных алгебраических уравнений методом Ньютона

Результат проекта (продукт)
Программа в среде программирования PascalABC

Индивидуальный план работы над проектом

Выбор руководителя и темы проекта.

Выбор типа проекта. Составление плана работы над проектом.

Работа над проектом

Анализ теоретической части.

Составление плана защиты проекта.

Отзыв руководителя. Формирование папки индивидуального проекта.

Защита индивидуального итогового проекта

Отзыв

на исследовательскую работу

учащегося 9 б класса МБОУ «Гимназия №7» г. Торжка

Смольков Андрей Владимирович

по теме: «Программирование решения уравнений»

Работа Смолькова Андрея представляет собой исследование программирование решения уравнений. Актуальность работы заключается в том, что на данный момент учащиеся 9-х классов изучают язык программирования Паскаль, и возникла необходимость объединить математику и информатику в единый программный продукт. В работе важно разобраться с различными методами решения уравнений и написать программу. Содержание работы соответствует заявленной теме. Работа включает в себя основную часть, заключение, список литературы. Работу Андрей выполнял самостоятельно, используя материалы Интернета и литературы. При выполнения работы Андрей проявил: самостоятельность, способность решать соответствующие проблемы. Не выполнял все рекомендации научного руководителя и не вовремя устранял замечания. Замечания по данной работе значительные, необходимо продумать и доработать заключение по данной теме. Не достаточно теоретического материала по языку программирования и их разновидности.

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

Учитель информатики . Борисова О.А.

(предмет) (подпись) (расшифровка подписи)

«__»_____________ 2018 г.

Общие сведения о языке программирования Паскаль

Языки программирования — это формальные языки, предназначенные для записи алгоритмов, исполнителем которых будет компьютер. Записи алгоритмов на языках программирования называются программами. Существует несколько тысяч языков программирования. Для данного проекта выбран язык программирования Паскаль, который был разработан в 70-х годах прошлого века Никлаусом Виртом (Швейцария). свое название этот язык получил в честь французского ученого Блеза Паскаля, известного не только своими достижениями в математике, физике и философии, но и созданием первой в мире механической машины, выполнявшей сложение двух чисел.

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

Основой языка программирования Паскаль, как и любого другого языка, является алфавит — набор допустимых символов, которые можно использовать для записи программы. Это:

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

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

В программе, записанной на языке Паскаль, можно выделить:

1. заголовок программы;
2. блок описания используемых данных;
3. блок описания действий по преобразованию данных (программный блок).

Заголовок программы состоит из служебного слова program и имени программы. После имени программы ставятся точка с запятой. Блок описания данных состоит из раздела описания констант (const), раздела описания переменных (var) и некоторых других разделов. В разделе описания переменных указываются имена используемых в программе переменных и их типы. Имена переменных одного типа перечисляются через запятую, затем после двоеточия указывается их тип; описание каждого типа заканчивается точкой с запятой.

Общий вид программы:

Решение системы алгебраических уравнений методом Гаусса

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

В переменную n вводится порядок матрицы системы. С помощью вспомогательной процедуры Input вводятся двумерный массив A и одномерный массив b, после чего оба массива и переменная n передаются функции Gauss. В функции Gauss для каждого k-го шага вычислений выполняется поиск максимального элемента в k-м столбце матрицы начиная с k-й строки. Номер строки, содержащей максимальный элемент сохраняется в переменной l. В том случае если максимальный элемент находится не в k-й строке, строки с номерами k и l меняются местами. Если же все эти элементы равны нулю, то происходит прекращение выполнения функции Gauss c результатом false. После выбора строки выполняется преобразование матрицы по методу Гаусса.

Решение нелинейных уравнений

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

Дана непрерывная функция f(x), которая содержит единственный корень на отрезке [a,b], где b>a при чем определены непрерывны и сохраняют знак f`(x) f«(x). Точность е. Выбираем грубое приближение корня х 0 . Найдем значение функции точке х 0 и проведем касательную до пересечения с осью абсцисс, получим значение х 1 . Определим значение функции в точке х 1 , через эту точку проводим касательную и получаем точку х 2 . Повторим этот процесс n раз.

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

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

Заключение

Практически перед каждым программистом рано или поздно встает задача определения корней уравнения. На сегодняшний день существует достаточно много алгоритмов решения данной задачи. Все они могут быть разделены на два этапа: отделения и уточнения корней. Первую часть легко выполнить графическим методом. Для выполнения второго этапа решения уравнения можно воспользоваться одним из многих методов уточнения корней уравнения.

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

Список литературы

1. Босова Л.Л. Информатика: учебник для 8 класса/ Л.Л. босова, А.Ю. Босова.-3-е изд.-М.: БИНОМ. Лаборатория знаний, 2015. — 160с.:ил.
2. http://www.cyberforum.ru
3. http://tpdn.ru/library/articles/52/13520
4. http://pcfu.ru/metod-gaussa-dlya-resheniya-slau

Текст публичного выступления

Здравствуйте уважаемые члены комиссии. Я Смольков Андрей, ученик 9Б класса МБОУ «Гимназии №7» города Торжка. Разрешите представить свой исследовательский проект по теме «Программирование решения уравнений». Языки программирования — это формальные языки, предназначенные для записи алгоритмов, исполнителем которых будет компьютер. Записи алгоритмов на языках программирования называются программами. Существует несколько тысяч языков программирования. Для данного проекта выбран язык программирования Паскаль, который был разработан в 70-х годах прошлого века Никлаусом Виртом (Швейцария). Свое название этот язык получил в честь французского ученого Блеза Паскаля, известного не только своими достижениями в математике, физике и философии, но и созданием первой в мире механической машины, выполнявшей сложение двух чисел. Язык Паскаль считается универсальным языком программирования, так как он может применяться для записи алгоритмов решения самых разных задач ( вычислительных, обработки текстов, построения графических изображений, поиска информации и т.д.). Он поддерживает процедурный стиль программирования, в соответствии с которым программа представляет собой последовательность операторов, задающих те или иные действия. Основой языка программирования Паскаль, как и любого другого языка, является алфавит — набор допустимых символов, которые можно использовать для записи программы. Это: латинские прописные буквы; латинские строчные буквы; арабские цифры; специальные символы (знак подчеркивания, знаки препинания, круглые, квадратные и фигурные скобки, знаки арифметических операций и д.р.). В языке существует также некоторое количество различных цепочек символов, рассматриваемых как единые смысловые элементы с фиксированным значением. Такие цепочки символов называются служебными словами. В программе, записанной на языке Паскаль, можно выделить: заголовок программы; блок описания используемых данных; блок описания действий по преобразованию данных (программный блок). Заголовок программы состоит из служебного слова program и имени программы. После имени программы ставятся точка с запятой. Блок описания данных состоит из раздела описания констант (const), раздела описания переменных (var) и некоторых других разделов. В разделе описания переменных указываются имена используемых в программе переменных и их типы. Имена переменных одного типа перечисляются через запятую, затем после двоеточия указывается их тип; описание каждого типа заканчивается точкой с запятой. Общий вид программы:

Метод Гаусса — классический метод решения системы линейных алгебраических уравнений. Назван в честь немецкого математика Карла Фридриха Гаусса. Это метод последовательного исключения переменных, когда с помощью элементарных преобразований система уравнений приводится к равносильной системе треугольного вида, из которой последовательно, начиная с последних (по номеру), находятся все переменные системы. На данных слайдах представлен программный продукт реализации решения уравнения методом Гаусса в Паскале. Метод Ньютона , алгоритм Ньютона (также известный как метод касательных ) — это итерационный численный метод нахождения корня заданной функции. Дана непрерывная функция f(x), которая содержит единственный корень на отрезке [a,b], где b>a при чем определены непрерывны и сохраняют знак f`(x) f«(x). Точность е. Выбираем грубое приближение корня х 0 . Найдем значение функции точке х 0 и проведем касательную до пересечения с осью абсцисс, получим значение х 1 . Определим значение функции в точке х 1 , через эту точку проводим касательную и получаем точку х 2 . Повторим этот процесс n раз. Программа на слайде. К сожалению, при всех своих достоинствах метод Ньютона не гарантирует сходимости. Отсутствия решения может возникнуть по нескольким причинам. Например, это может произойти из-за того, что касательная будет параллельна оси абсцисс. В этом случаи необходимо предусмотреть выход из цикла при достижении большого количества итераций. Практически перед каждым программистом рано или поздно встает задача определения корней уравнения. На сегодняшний день существует достаточно много алгоритмов решения данной задачи. Все они могут быть разделены на два этапа: отделения и уточнения корней. Первую часть легко выполнить графическим методом. Для выполнения второго этапа решения уравнения можно воспользоваться одним из многих методов уточнения корней уравнения.

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

Линейный алгоритм

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

Структура программы на языке Паскаль

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

Заголовок программы

Текст программы начинается со слова program. После него записывается имя программы. Данная строка носит информативный характер и ее можно не писать.

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

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

Раздел описания переменных

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

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

В нашем примере переменные с именами X и Y используются для хранения исходных данных. Переменная с именем Z используется для хранения результата вычислений.

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

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

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

Тело программы

Все что находится между служебными словами Begin и end — тело программы. Здесь записываются основные команды.

Оператор присваивания значений переменным имеет следующую структуру: переменная := выражение

Значок : = (двоеточие, равно) читается как «присвоить».
Умножение обозначается символом * (звездочка), деление — символом / (слеш).

Вывод результата выполняет команда write или print.

Каждая строка содержащая команду на языке Паскаль обязательно заканчивается символом «точка с запятой«.

Команды в Паскаль для ввода и вывода данных

Команда Read

В первом примере мы присвоили значения переменным непосредственно в тексте программы. Но так как программа пишется для решения множества однотипных задач, то удобнее задавать значения переменным во время ее работы. Для этого применяется команда read, которая позволяет ввести текстовые или числовые данные с клавиатуры.

Модифицируем код программы из примера выше.

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

При работающей программе в системе программирования PascalABC появится строка ввода данных. Там и пишутся значения переменных.

Команда Write

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

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

У нас появились подсказки. Посмотрите на команду write. В качестве ее аргумента был использован текст, заключенный в апострофы. И еще, появилось окончание ln у оператора write. Именно оно заставляет последующий вывод информации делать с новой строки. Это же окончание можно использовать совместно с оператором read.

Readln и Writeln в паскале — это модифицированные команды Read и Write. В командах добавлено окончание ln (line new — новая строка). Такая форма операторов делает последующий вывод информации, при работе программы, с новой строки.

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

Примеры программ на паскале — задания на линейные алгоритмы

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

Решение:

Задание 2. Дана длина ребра куба а. Найти объем куба V=a 3 и площадь его поверхности S=6a 2 .

🐍 Линейное программирование. Практика решения задач оптимизации на Python

Leo Matyushkin

Данная публикация представляет собой сокращенный перевод руководства Мирко Стожилковича Hands-On Linear Programming: Optimization With Python. Для удобства читателей текст перевода также адаптирован в виде Jupyter-блокнота.

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

Экосистема Python включает несколько мощных инструментов линейного программирования. Из этого руководства вы узнаете:

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

Что собой представляет линейное программирование

Системы линейных уравнений и неравенств часто имеют множество возможных решений.

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

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

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

Особенно важным видом целочисленных переменных являются бинарные переменные, имеющие лишь значения 0 или 1 , и полезные при принятии решений вида «да»/«нет». Например, следует ли строить завод, включить или выключить машину. Также их можно использовать для имитации логических ограничений.

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

Линейное программирование на Python

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

Заметим, что почти все широко используемые библиотеки линейного программирования и смешанно-целочисленного линейного программирования написаны на языках Fortran, C или C++, так как линейное программирование требует интенсивной вычислительной работы с матрицами, часто очень большими. Соответствующие инструменты Python – это просто удобные интерфейсы для работы с низкоуровневыми библиотеками – солверами.

В этом руководстве для определения и решения задач линейного программирования мы будем использовать Python-библиотеки SciPy и PuLP.

1. Примеры задач линейного программирования

1.1. Небольшой показательный пример

Рассмотрим следующую задачу максимизации:

Нам нужно найти такие x и y , чтобы выполнялись «красное», «синее» и «желтое» неравенства, а также ограничения x ≥ 0 и y ≥ 0 . При этом решение должно соответствовать максимально возможному значению z .

Независимые переменные, которые нужно найти ( x и y ) называют переменными решения (decision variables). Функция, которую необходимо максимизировать или минимизировать ( z ), – это целевая функция (objective function), функция стоимости (cost function) или просто цель (goal). Неравенства (или уравнения), которым необходимо удовлетворять, называются ограничениями (inequality constraints или equality constraints для обычных уравнений).

Проблему можно визуализировать следующим образом.

2x + y = 20 , а красная область над ней показывает, где красное неравенство не выполняется. Аналогично синяя линия – это −4x + 5y = 10 , желтая линия – это −x + 2y = −2 , окрашенные области – та часть плоскости, где неравенство не выполняется.» data-src=»https://media.proglib.io/posts/2020/11/26/5a6c3e3ee24ae5a228d7a0ee4ea9fb8a.png» > Красная линия представляет функцию 2x + y = 20 , а красная область над ней показывает, где красное неравенство не выполняется. Аналогично синяя линия – это −4x + 5y = 10 , желтая линия – это −x + 2y = −2 , окрашенные области – та часть плоскости, где неравенство не выполняется.

Каждая точка серой области удовлетворяет всем ограничениям и является потенциальным решением задачи. Эта область называется областью допустимых решений (feasible region), а ее точки – допустимыми решениями (feasible solutions).

Мы хотим максимизировать z . Решение, соответствующее максимальному значению z , называют оптимальным решением.

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

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

Его можно визуализировать, добавив соответствующую зеленую прямую:

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

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

Больше нет зеленой линии – только дискретные точки, где значение x является целым числом. Возможные решения – это зеленые точки на сером фоне.

Эти три примера иллюстрируют задачи линейного программирования – они имеют ограниченные допустимые области решений и конечные решения.

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

1.2. Задача о распределении ресурсов

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

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

1. Прибыль (profit) на единицу продукта составляет 20, 12, 40 и 25 долларов для каждого из четырех продуктов соответственно.
2. Из-за нехватки рабочей силы (manpower) общее количество единиц, производимых в день, не может превышать 50.
3. На каждую единицу 1-го продукта расходуется 3 единицы сырья A. Каждая единица 2-го продукта требует 2 единиц сырья A и 1 единицы сырья B. Каждой единице 3-го продукта требуется 1 единица A и 2 единицы B. Наконец, каждая единица 4-го продукта требует трех единиц. B.
4. Из-за ограничений по транспортировке и хранению фабрика может потреблять до 100 единиц сырья A и 90 единиц B в день.

Математическую модель можно определить так:

Целевая функция (прибыль) определяется в условии 1. Ограничение рабочей силы следует из условия 2. Ограничения на сырье A и B могут быть получены из условий 3 и 4 путем суммирования потребностей в сырье для каждого продукта. Наконец, количество продуктов не может быть отрицательным.

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

2. Линейное программирование на Python. Практическая реализация

В этом руководстве мы будем использовать для решения описанной выше задачи линейного программирования два пакета Python :

1. SciPy – универсальный пакет для научных вычислений с Python. Его внутренний пакет scipy.optimize можно использовать как для линейной, так и для нелинейной оптимизации.
2. PuLP – API линейного программирования Python для определения задачи и вызова солверов. По умолчанию в качестве солвера используется COIN-OR Branch and Cut Solver (CBC). Еще один отличный солвер с открытым исходным кодом – GNU Linear Programming Kit (GLPK).

2.1. Установка SciPy и PuLP

Чтобы следовать этому руководству, вам необходимо установить SciPy и PuLP.

Возможно, вам потребуется запустить pulptest или sudo pulptest , чтобы включить солверы PuLP, особенно если вы используете Linux или Mac:

2.2. Использование SciPy

В этом разделе мы рассмотрим, как использовать библиотеку SciPy по оптимизации и поиску корней для линейного программирования. Начнём с импорта scipy.optimize.linprog() :

2.3. Решение первого примера c помощью SciPy

Начнём с решения первого (дополненного) примера:

linprog() решает только задачи минимизации (не максимизации) и не допускает ограничений-неравенств со знаком больше или равно ( ≥ ). Чтобы обойти эти проблемы, нам необходимо изменить описание задачи перед запуском оптимизации:

• Вместо максимизации z = x + 2y минимизируем отрицательное значение ( −z = −x − 2y ).
• Вместо знака ≥ мы можем умножить «желтое» неравенство на -1 и получить противоположный знак (ограничения по осям рассмотрим далее).

На следующем шаге определяем входные значения:

Мы поместили значения из системы в соответствующие списки:

• obj содержит коэффициенты целевой функции,
• lhs_ineq и rhs_ineq содержат коэффициенты из ограничений-неравенств,
• lhs_eq и rhs_eq содержат коэффициенты из ограничивающего уравнения.

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

Однако эти границы совпадают с установленными по умолчанию в linprog() .

Наконец, пришло время оптимизировать и решить интересующую нас проблему:

Параметр c относится к коэффициентам из целевой функции. A_ub и b_ub соответственно связаны с коэффициентами из левой и правой частей ограничений-неравенств. Точно так же A_eq и b_eq относятся к ограничениям уравнений. Параметр bounds служит для указания нижней и верхней границ переменных решения.

Параметр method определяет используемый алгоритм линейного программирования. Доступны три варианта:

• по умолчанию используется метод внутренней точки: method = «inner-point»,
• измененный двухфазный симплекс-метод method=»revised simplex»,
• симплекс-метод method=»simplex»

linprog() возвращает структуру данных со следующими атрибутами:

• .con – остатки ограничения-равенства;
• .fun – оптимальное значение целевой функции (если найдено);
• .message – словесный статус решения;
• .nit – количество итераций, необходимых для завершения расчета;
• .slack – значения так называемых дополнительных переменных – разниц между значениями левой и правой сторонами ограничений;
• .status – целое число от 0 до 4, отражающих результат решения: например, 0, когда было найдено оптимальное решение;
• .success – логическое значение, показывающее, найдено ли оптимальное решение;
• .x – массив NumPy, содержащий оптимальные значения переменных решения.

Доступ к атрибутам можно получить по отдельности:

Графически результат можно отобразить следующим образом.

Вначале наша задача органичивалась только неравенствами. Если удалить параметры зеленого уравнения A_eq и b_eq из вызова linprog() , получим следующий результат:

2.4. Решение задачи о производстве с помощью SciPy

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

Как и в предыдущем примере, нам нужно извлечь необходимые векторы и матрицу из задачи, передать их в качестве аргументов в linprog() :

Максимальная прибыль составляет 1900 и соответствует x_1 = 5 и x_3 = 45 . В данных условиях производить второй и четвертый продукты невыгодно. Результат позволяет сделать несколько интересных выводов:

1. Третий продукт приносит наибольшую прибыль.
2. Первая дополнительная переменная ( slack ) равна 0. Это означает, что равны значения левой и правой сторон ограничения для рабочей силы. Завод производит 50 единиц в день, и это его полная мощность.
3. Вторая дополнительная переменная равна 40: фабрика потребляет 60 единиц сырья A (15 единиц для первого продукта и 45 для третьего) из возможных 100 единиц.
4. Третья дополнительная переменная равен 0: фабрика потребляет все 90 единиц сырья B. При этом все это количество потребляется для производства третьего продукта. Вот почему фабрика вообще не может производить второй или четвертый товар и не может произвести более 45 единиц третьего товара. Cырья B просто не хватает.

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

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

2.5. Решение первой задачи на линейное программирование с помощью PuLP

Итак, PuLP имеет более удобный API линейного программирования, чем SciPy. Начнем с импорта.

Первый шаг – инициализировать экземпляр LpProblem для описания модели:

Параметр sense определяет, решаем ли мы задачу минимизации (параметр LpMinimize или 1 , установлен по умолчанию) или максимизации ( LpMaximize или -1 ).

Создав модель, мы можем определить переменные решения как экземпляры класса LpVariable :

Значения границ по умолчанию – отрицательная и положительная бесконечности, поэтому в нашем случае необходимо указать нижнюю границу ( lowBound = 0 ).

Необязательный параметр cat определяет категорию переменной решения. При работе с непрерывными переменными можно использовать значение по умолчанию «Continuous» .

Переменные x и y теперь можно использовать для создания других PuLP-объектов, представляющих линейные выражения и ограничения:

Построив линейную комбинацию нескольких переменных решения, мы получаем экземпляр pulp.LpAffineExpression , представляющий линейное выражение. Выражения можно комбинировать с операторами == , и >= и получать экземпляры pulp.LpConstraint – линейные ограничения вашей модели.

Опишем теперь ограничения. В отличие от SciPy, с PuLP не нужно создавать списки и матрицы. Просто записываем выражения Python и добавляем в модель с помощью оператора += :

LpProblem позволяет добавлять ограничения в модель, определяя их как кортежи. Первый элемент кортежа – экземпляр LpConstraint , второй – его удобочитаемое имя.

Аналогично описывается целевая функция:

Теперь можно посмотреть полное определение модели:

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

Теперь мы готовы решить задачу. Достаточно лишь вызвать метод .solve() для объекта модели.

Метод .solve() вызывает базовый солвер, изменяет объект модели и возвращает целочисленный статус решения, равный 1, если найден оптимум. Остальные коды состояний описаны в документации.

Результаты оптимизации доступны в виде атрибутов модели:

model.objective содержит значение целевой функции, model.constraints – значения дополнительных переменных, а объекты x и y имеют оптимальные значения переменных решения.

Результаты получились примерно такие же, как у SciPy.

Чтобы получить смешанно-целочисленное решение, достаточно обозначить это при помощи параметра cat :

Теперь x – целое число, как указано в модели. Этот факт меняет решение. Покажем это на графике:

Как видите, оптимальным решением является крайняя правая зеленая точка на сером фоне. Это решение с наибольшими значениями как x , так и y , дающее максимальное значение целевой функции.

2.6. Решение задачи о производстве с помощью PuLP

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

Как видите, решение согласуется с тем, что мы молучили с помощью SciPy. Наиболее выгодное решение – производить в день 5 единиц первого продукта и 45 единиц третьего.

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

Теперь у нас есть еще одно логическое ограничение: если x_1 положительно, то x_3 должно равняться нулю, и наоборот. Здесь пригодятся бинарные переменные решения. Введем две переменные y_1 и y_3 , которые будут обозначать, генерируются ли вообще первый или третий продукты:

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

Заключение

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

Теперь – после прохождения этого руководства – вы умеете:

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

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

Следите за нашими тегами Python и Математика!