Математическая постановка задачи для линейного уравнения

Подробный разбор симплекс-метода

Пролог

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

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

§1. Постановка задачи линейного программирования

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

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

1. Неравенства с отрицательными умножаем на (-1).
2. Если неравенство вида (≤), то к левой части добавляем – добавочную переменную, и получаем равенство.
3. Если неравенство вида (≥), то из левой части вычитаем , и получаем равенство.
4. Делаем замену переменных:

• Если , то
• Если — любой, то , где

Замечание: Будем нумеровать по номеру неравенства, в которое мы его добавили.

Замечание: ≥0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

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

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит (т.е. – не внутренняя точка).

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

Определение: Пусть есть система m уравнений и n неизвестных (m

Решение текстовых задач с помощью линейных уравнений

Содержание

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

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

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

Текстовая задача – описание с помощью слов какой-то ситуации, где в итоге требуется что-то из перечисленного:
— дать количественную характеристику какого-то элемента этой ситуации
— установить наличие какого-то отношения между элементами (либо его отсутствие)
— определить вид этого отношения

О том, что такое линейное уравнение, мы говорили в предыдущем уроке.

Решение задачи и математическая модель

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

Почему важно научиться решать задачи? Часто они описывают какие-то реальные ситуации, которые вам будут попадаться в жизни дальше. И их придется решать.

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

Математическая модель — это способ описания реальной жизненной ситуации (задачи) с помощью математического языка.

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

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

Важно: Иногда бывает, что у задачи нет правильного ответа и нужно быть особо внимательным при его формулировке.

Рассмотрим на самом простом примере

Несколько ребят на уроке труда собирали яблоки в саду около школы. Всего они насобирали $29$ кг яблок. Каждый из учеников собрал по $4$ кг яблок. Сколько ребят собирали яблоки в саду около школы?

Составим уравнение, обозначив количество учеников за $x$. Получим: $$4x = 29$$ $$x = \frac <29><4>$$$$x = 7,25$$

У нас получилось нецелое число. Но может ли быть количество ребят нецелым числом? Конечно, нет, поэтому такая задача решения не имеет.

Ответ: решения нет.

Разберем другой пример.

Сейчас папе $46$ лет, а сыну $16$. Сколько лет назад папа был старше сына в $3$ раза?

Сначала найдем разницу в возрасте папы и сына: $$46-16 = 30$$ То есть, сын родился, когда папе было $30$ лет. Эта разница в возрасте будет сохраняться всю жизнь. Например, когда ребенку было $5$ лет, то папе все равно было на $30$ лет больше.

Теперь по условию задачи обозначим за $x$ возраст сына в момент, когда он был в 3 раза младше папы. Тогда папе в это же время было $3x$ лет. А разница между $3x$ и $x$, как мы выяснили, равна $30$ годам.

Составим уравнение: $$3x-x = 30$$ Упростим и решим его: $$2x = 30$$ $$x = 15 (лет)$$ Получили ли мы ответ? Еще нет, так как мы нашли только возраст сына. А в задаче требуется узнать, сколько лет назад случилась описанная ситуация. Если сейчас сыну $16$ лет, а тогда ему было $15$, то найдем разницу: $$16-15 = 1 (год)$$ То есть, мы выяснили, что папе было в $3$ раза больше, чем сыну один год назад. Это и будет ответом на нашу задачу.

Ответ: $1$ год назад.

Как видите, в данном задании найденный корень уравнения еще не был нужным нам ответом, и необходимо было решать дальше.

Важно: корень составленного к задаче уравнения – это часто еще не ответ на поставленный в ней вопрос!

Этапы решения заданий с помощью линейного уравнения

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

1. Выбрать, какую неизвестную величину обозначить за переменную $x$.
2. Через введенную переменную выразить остальные неизвестные величины.
3. На основе имеющихся данных составить уравнение и решить его.
4. При необходимости найти другие неизвестные величины.
5. Проанализировать, соответствуют ли полученные результаты смыслу задачи.
6. Сформулировать и записать ответ.

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

К примеру, решим такую задачу: в столовой на одной полке было в $2$ раза больше кружек, чем на другой. Перед очередным классом с первой полки взяли $16$ кружек, но потом на другую поставили $4$. В итоге на обеих полках оказалось одинаковое количество кружек. Найдите, сколько на каждой полке кружек было первоначально.

Решение. Обозначим исходное количество кружек на второй полке за $x$ и составим таблицу:

Так как по условию задачи кружек на обеих полках стало поровну, то $$2x-16 = x+4$$ Упростим и решим, перенеся $x$ влево, а $16$ вправо с противоположным знаком: $$2x-x = 16+4$$ $$x=20$$ Так мы нашли исходное количество кружек на второй полке. Тогда на первой полке было: $$20\times 2 = 40 (кружек)$$

Ответ: на первой полке было $40$ кружек, а на второй $20$.

Алгебра. 7 класс

Конспект урока

Решение задач с помощью линейных уравнений

Перечень рассматриваемых вопросов:

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

Уравнение – это равенство, включающее в себя переменную, значение которой нужно вычислить.

Корень уравнения – это число, при подстановке которого в уравнение получается верное равенство.

Решить уравнение – значит найти все его корни или установить, что их нет.

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

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

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

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

Свободный член – член уравнения, не содержащий неизвестного.

Уравнение – это равенство, включающее в себя переменную, значение которой нужно вычислить.

Решить уравнение – значит найти все его корни или установить, что их нет.

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

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

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

Линейное уравнение – уравнение вида ax = b, где x – переменная, a, b – некоторые числа.

1. Никольский С. М. Алгебра: 7 класс. // Никольский С. М., Потапов М. К., Решетников Н. Н., Шевкин А. В. – М.: Просвещение, 2017. – 287 с.

1. Чулков П. В. Алгебра: тематические тесты 7 класс. // Чулков П. В. – М.: Просвещение, 2014 – 95 с.

2. Потапов М. К. Алгебра: дидактические материалы 7 класс. // Потапов М. К., Шевкин А. В. – М.: Просвещение, 2017. – 96 с.

3. Потапов М. К. Рабочая тетрадь по алгебре 7 класс: к учебнику С. М. Никольского и др. «Алгебра: 7 класс». 1, 2 ч. // Потапов М. К., Шевкин А. В. – М.: Просвещение, 2017. – 160 с.

Теоретический материал для самостоятельного изучения.

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

Решить задачу можно с помощью системы уравнений, а можно с помощью одного уравнения. Рассмотрим на примере задачи.

Из города А в город В одновременно выехали два автомобиля. Первый проехал с постоянной скоростью весь путь. Второй проехал первую половину пути со скоростью, меньшей скорости первого на 15 км/ч, а вторую половину пути – со скоростью 90 км/ч, в результате чего прибыл в В одновременно с первым автомобилем. Найдите скорость первого автомобиля, если известно, что она больше 54 км/ч. Ответ дайте в км/ч.

При решения текстовых задач эффективно построение схем и составление таблиц.

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

Скорость первого автомобиля: x, скорость второго автомобиля: x – 15x – 15/

Теперь заполним вспомогательную таблицу.

Условие, что автомобили прибыли в пункт назначения одновременно, используем для составления уравнения. Выражаем время первого автомобиля, которое он затратил на весь путь, через x.

Время первого автомобиля:

Время второго автомобиля:

Сократим на S ≠ 0 и умножим на 2.

Умножим обе части на 90x(x – 15), получим:

Решением уравнения будут корни:

Условию уравнения удовлетворяет только x = 60

Ответ: 60 км/ч – скорость первого автомобиля.

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

Решать задачу с помощью уравнения следует в такой последовательности:

1) обозначить переменной одну из неизвестных величин;

2) другие неизвестные величины (если они есть) выразить через введенную переменную;

3) по условию задачи установить соотношение между неизвестными и известными значениями величин и составить уравнение;

4) решить полученное уравнение;

5) проанализировать решение уравнения и найти неизвестную величину, а при необходимости и значения остальных неизвестных величин;

6) записать ответ к задаче.

Решите задачу двумя способами.

В первый день со склада было отпущено 20% имевшихся груш. Во второй день 180% от того количества груш, которое было отпущено в первый день. В третий день ‑ оставшиеся 88 кг. Сколько кг груш было на складе первоначально?

Разберем 2 способа решения этой задачи.

Для первого способа составим вспомогательную таблицу:

Значит, первоначально было 200 кг груш.

Составим вспомогательную аблицу:

Ответ: 200 кг груш.

Разбор заданий тренировочного модуля.

Задание 1. Запишите выражение для нахождения цены 1 кг сахара (в руб.), если n тонн сахара стоят m рублей.

Для решения задачи, вспомним, сколько килограммов содержится в одной тонне:

Так как стоимость n тонн сахара = m рублей, то, чтобы найти, сколько стоит 1 кг сахара, нужно стоимость разделить на количество:

Цена персиков на 30 р. выше, чем цена абрикосов. Для консервирования компота купили 5 кг персиков и 7 кг абрикосов. По какой цене покупали фрукты, если вся покупка обошлась 850 рублей?

Пусть цена абрикосов – x рублей. Тогда x + 20x + 20 – цена персиков.

Всего купили персиков: 5(x + 30) и абрикосов 7x.

Так как на всю покупку затратили 850 руб., имеем выражение:

5(x + 30) + 7x = 850

Раскроем скобки: 5x + 150 + 7x = 850

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