0. Короткое введение

На Хабре уже были публикации о симплекс-методе раз и два. И они очень даже не плохи. Но проблема в том, что обычно симплекс-метод не изучают в школе, при этом школьники уже обладают достаточным багажом знаний для освоения этого метода. И попытка объяснить его школьникам была сделана в августовском номере журнала "Юный техник" за 1985 год. Я хочу привести эту статью здесь, а также добавить свои комментарии по поводу примера, разобранного в ней. Автор статьи: С.Волков. Рисунки Г.Заславской. Статья была размещена в рубрике "ЭВМ в твоих руках".

В процессе работы над настоящей статьёй для Хабра я написал письмо в редакцию журнала Юный техник с просьбой разрешить мне привести текст оригинальной статьи здесь полностью. И редактор дал мне такое разрешение! При том ответ пришёл очень быстро.

В настоящей статье я собираюсь сделать вот что:
1) Привести ссылку на скан оригинальной статьи (вот она: Путешествие в космос)
2) Привести текст самой статьи в перенабранном виде с тем, чтоб вам было удобней читать, а мне — ссылаться.
3) Чуть-чуть покритиковать эту статью, несмотря на то, что и сам журнал и статья эта мне очень нравятся! Разобрать, как можно было бы объяснить решение более понятно для школьников.
4) Всё-таки решить эту задачу с помощью ЭВМ.

Цель данной статьи на Хабре... ну, наверно, в том, чтоб, с одной стороны, вскрыть эдакую капсулу времени, а с другой, привлечь внимание учителей и школьников к этому методу. Всё-таки сама статья в ЮТ вышла уже больше 37 лет назад и вряд ли о ней часто вспоминают.

И ещё кое-что... Есть поговорка про то, что если дать человеку рыбу — он будет сыт один день, а если научить его ловить рыбу — он будет сыт до конца жизни. Вот по-моему, симплекс-метод — это способ ловли рыбы. Грубо говоря, некоторые знания или навыки, которые можно получить даже будучи школьником — фактически могут составлять основу для целой профессии. Симплекс-метод — это как раз одно из таких умений. Этот метод используется очень много где, где нужно что-либо оптимизировать: например, для оптимизации маршрутов перевозки товаров; для оптимизации раскроя листовых материалов в производстве; в военном деле (для оптимизации логистики при перевозке боеприпасов и эвакуации раненых); в бизнесе для планирования затрат и доходов, принятия решения о том, кого нанять и кого уволить; в экономике и стратегическом планировании (кстати, очень многих войн попросту не случилось бы, если бы люди, которые их начинали — знали бы об этом методе). И при этом, освоить его может даже семиклассник. Необходимый для понимания минимум — умение решать системы линейных уравнений. Т.е. это даже не одна профессия, а целый букет. Звучит заманчиво? Тогда давайте же скорее начнём!

1. Ссылка на скан оригинальной статьи.

вот она: Путешествие в космос

2. Путешествие в космос (Юный техник, №8, 1985 год)

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

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

— Топливо — нуль,— объяв­ляет бортовой компьютер.

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

На станции два вида топлива (естественно, оно необычно); топливо номер один называет­ся «Антигравитон-10», другое «Антигравитон-7», сокращенно А-10 и А-7. Цифра в названии топлива показывает, сколько ча­сов можно пролететь на одном его литре; топливный бак звез­долета вмещает 5 л.

Какое же топливо выбрать? Очевидно, А-10 эффективнее, но 1 л его весит 3 кг, а общий вec топлива на борту нашего космолета не должен превышать 12 кг. Литр А-7 весит 2 кг. Можно залить им полный бак, он будет весить всего 10 кг, но запас хода окажется равным 35 часам.

Есть еще вариант: залить в бак сразу оба сорта топлива (они не перемешиваются) и ис­пользовать их поочередно. Но какого топлива сколько взять на борт?

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

Итак, 1 л антигравитона А-7 — это 7 часов полета. Значит, если мы возьмем на борт Х₁ литров, то летное время составит 7X₁ ча­сов. Точно так же Х₂ литров А-10 гарантируют нам 10Х₂ лет­ных часов, а всего летное время составит

часов.

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

Во-вторых, вес топлива не должен превышать 12 кг. Литр А-10 весит 3 кг, значит, общий вес топлива этого сорта будет 3Х₂, а литр А-7, как сказано, весит 2 кг. Его вес равен 2Х₁, а всего горючее весит

У нас получилась следующая задача:

максимизировать

при ограничениях

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,ㅤㅤㅤㅤㅤㅤㅤ(5)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

Для решения ее прежде все­го надо заменить неравенства равенствами. Если мы зальем меньше 5 л топлива, то какой-то объем бака останется неис­пользованным, обозначим его через Х₃. Тогда сумма объема топлива и пустой части бака даст нам как раз 5 л, то есть

Точно так же поступим и с ве­совым ограничением. Неисполь­зованный вес назовем Х₄ и в конце концов перепишем нашу задачку так:

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,ㅤㅤㅤㅤㅤ(7)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

Любое решение этой системы даст нам объемы каждого сорта топлива, полетное время и вели­чины неиспользованных объема и веса. Но переменных пять, а уравнений только три, значит, система имеет не одно реше­ние. Мы должны найти такое, когда Т — летное время — бу­дет максимальным. Предполо­жим, что мы вообще не заправи­ли космолет, то есть Х₁=Х₂=0. Тогда, естественно, летать прос­то невозможно, Т=0, а Х₃=5 и Х₄=12. Мы получили одно из решений нашей системы, конеч­но, не наилучшее. Это решение называют исходным опорным планом. Переменные, входящие в опорный план, называют ба­зисными переменными или про­сто базисом. В нашем случае это Т, Х₃ и Х₄. Обратите внима­ние: каждая базисная перемен­ная входит только в одно урав­нение и коэффициент при ней равен 1. Так как же улучшить опорный план? Для начала начнем заправку космолета. Только не будем заливать оба сорта топлива сра­зу, возьмем только один.

С точ­ки зрения математики это будет означать, что либо Х₁ —объем А-7, либо Х₂— объем А-10— станет отличным от нуля, то есть одна из этих переменных пой­дет в базис. Какое же топливо залить, или, что то же самое, какую переменную ввести в ба­зис? Наверное, Х₂.

А-10 эффек­тивнее, и введение в базис Х₂ сильнее влияет на Т. Это видно и из нашей системы. В самом деле, коэффициент при Х₂ ра­вен 10. Значит, увеличение Х₂ на 1 уменьшает левую часть на 10. Чтобы равенство сохрани­лось, приходится увеличить Т тоже на 10. Тогда как увеличе­ние на единицу Х₁ приводит к возрастанию Т только на 7. Вот мы и получили первое правило симплекс-метода: в базис вво­дится та переменная, которая имеет наибольший по абсолют­ной величине отрицательный коэффициент. А количество А-10, которое нужно залить, оп­ределяют ограничения. Ведь при заполнении бака уменьшаются пустой объем Х₃ и неис­пользованный вес Х₄. Какая-то из этих величин в конце концов обратится в нуль — или бак окажется наполнен, или лимит веса будет исчерпан.

А это, кстати, означает, что переменная, которая стала рав­ной 0, исключится из базиса. Какую же исключить — Х₃ или Х₄?

Из второго соотношения сле­дует, что если Х₂ увеличить на 1, то Х₃ уменьшится на столько же. А начальное значение пу­стого объема было 5. Значит, максимальная величина Х₂ не может быть больше 5. Ведь нельзя залить топлива больше, чем вмещает бак.

В третьем соотношении уве­личение Х₂ на единицу умень­шает Х₄ сразу на 3, ведь 1 л ве­сит 3 кг. Именно на столько убы­вает неиспользованный вес при добавлении каждого литра топ­лива. А всего можно залить 12:3=4 л. В результате получаем, что Х₂ не превышает 4. Ну что ж, зальем 4 л А-10, при этом лимит веса будет исчерпан 2X₄=0. Эта переменная исклю­чается из базиса, а вместо нее входит Х₂.

Вот мы и получили второе правило симплекс-метода: но­вая базисная переменная уве­личивается до тех пор, пока ка­кая-нибудь из переменных ста­рого базиса не обратится в нуль. Теперь в новый базис входят Т, Х₃ и Х₂. Значит, надо соответ­ственно преобразовать систему уравнений, чтобы Х₂ присутст­вовало только в одном уравне­нии, в третьем, с коэффициен­том 1.

Для этого разделим послед­нее уравнение на 3, затем выч­тем его из второго. Тогда пе­ременная Х₂ исключится из второго уравнения. Потом иск­лючим Х₂ и из первого.

Роль бортового компьютера поручим микрокалькулятору. Прежде всего разделим на 3 все коэффициенты третьего уравнения. Получим:

теперь вычтем из его второго — 1 ; «-»; 0.666667;=.

На индикаторе появится число 0.333333. Наша система уравне­ний примет такой вид:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ ,
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,ㅤㅤㅤㅤ(9)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,

Теперь все переменные, кро­ме базисных — Т, Х₃ и Х₂,— полагаем равными 0 и получа­ем: Т=40, Х₃=1, Х₂=4. Это уже неплохо: 40 часов полета. Но можно сделать и лучше. В пер­вом уравнении коэффициент при Х₁ отрицателен, значит, вводя в опорный план эту пере­менную, можно увеличить Т. А для этого еще раз проделаем подобные вычисления, исклю­чим Х₁ из первого и третьего уравнений, а во втором коэф­фициент сделаем равным 1. Вот что получится:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ(10)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,

Отсюда ясно, что если залить 3 л А-7 и 2 л А-10, тогда наш космолет сможет летать 41 час. Пора давать задание роботу-заправщику.

Помогают графики

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

Дело в том, что все переменные входят в уравнения и неравен­ства в первой степени, или, как говорят математики, линейно. А теперь давайте посмотрим, не поможет ли нам график в ре­шении задачи линейного про­граммирования. Только прежде условимся, что оси координат мы будем называть не X и У, а Х₁ и Х₂. Давайте возьмем одно из ограничений нашей задачи и найдем на коорди­натной плоскости те точки, ко­торые ему удовлетворяют (счи­тая, что X₁ и Х₂ больше нуля). Сначала рассмотрим равенство X₁+X₂=5. Построим график этой линии. Для этого найдем две точки: если Х₁=0, то Х₂=5 (точка А), и наоборот, X₁=5, а Х₂=0 (точка В). Соединим точки А и В (см. рис.). Неравенству задачи удовлетворяют точки, лежащие внутри треугольника ОАВ. Координаты каждой из них определяют величины пе­ременных Х₁ и Х₂. Аналогично проведем прямую CD, опреде­ляемую вторым ограничением (2X₁+3X₂=12). Она пересекает АВ в точке Е. Любая точка внут­ри или на границе четырех­угольника ОСЕВ представляет возможное решение нашей за­дачи. Обратите внимание: точ­ка Е как раз отвечает наилучше­му, оптимальному решению. Случайно ли это?

Надеемся, что вы поняли суть графического решения задачи линейного программирования. К сожалению, этот способ хоро­шо работает только при малом количестве переменных, в са­мых простейших задачах. В реальной ситуации, когда пере­менных много, компьютеру приходится отыскивать опти­мальное решение, переходя от одной к другой грани огромно­го тысячегранного тела. Про­цедура эта медленная, и если число переменных превышает 15—20 тысяч, то симплекс-ме­тод, по словам математиков, «выдыхается». Недавно 25-лет­ний математик Нарендре Кармакар нашел новый способ ре­шения задачи линейного программирования, при котором компьютер тратит гораздо меньше времени, чем при тра­диционном симплекс-методе. Программа Кармакара часть из возможных решений сразу от­брасывает, не тратя время на их просмотр, и после каждого шага деформирует многогранник.

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

Во саду ли, в огороде...

И здесь может помочь линей­ное программирование. Пред­ставьте себе, что ваш пришколь­ный участок площадью S вы ре­шили засеять тремя культурами (какие это культуры конкретно, неважно). Урожайность пер­вой— У₁ кг/м², второй — У₂ кг/м² и третьей — У₃ кг/м². Под первую надо внести Р₁ кг удобрений на м“, под вторую — Р₂ и под третью — Р₃, а всего вы имеете П кг удобрений. Поста­райтесь найти посевные площа­ди под каждой культурой так, чтобы урожай был наибольшим. При этом не забудьте о возни­кающих ограничениях. Составь­те задачу линейного програм­мирования, задайтесь конкрет­ными цифрами и попробуйте ее решить. Какие еще задачи на отыскание наилучшего решения вы можете придумать?

С. ВОЛКОВ

Рисунки Г. ЗАСЛАВСКОЙ

3. Комментарий, 37 лет спустя (немного моей критики)

Первое, и самое главное: одна из самых частых проблем, при объяснении любых разделов математики кому бы то ни было — мотивационная. Грубо говоря, очень трудно объяснить, например, что такое определитель матрицы, если человек не понимает, зачем ему нужно это знать. Довольно быстро объяснение станет просто нагромождением информации. Чтоб этого не было, нужно всегда связывать объяснение математических понятий с какими-то проблемами из реальной жизни. Т.е. должна быть какая-то зацепка, связь с реальной жизнью. И вот тут автор статьи и художница — большие молодцы. Формулировка задачи, иллюстрации, упоминание компьютера в самом начале, где бортовой компьютер говорит, что топлива — нуль — создают хороший мотивационный фон. Первый раз я прочитал эту статью, когда пошёл в первый класс. Ничего не понял, но мотивирующий осадок остался... Было понимание, что я пропустил что-то важное, очень интересное и нужное. Пока учился в школе — несколько раз возвращался к этой статье, пытаясь её понять. Т.е. с побудительной частью статьи — всё отлично.

Но давайте теперь поставим себя на место школьника (допустим, десятиклассника обычной, не математической школы, читающего эту статью в 1985 году). "Линейное программирование" и "симплекс-метод" — таких слов десятиклассник скорее всего никогда не слышал. Более того, статья выходит в рубрике "ЭВМ в твоих руках", в ней упоминается компьютер, расчёты предполагается делать с помощью микрокалькулятора. У ребёнка того (да и нашего) времени в таком контексте слово "программирование" ассоциируется исключительно с написанием программы для компьютера. Более того, номер журнала свёрстан таким образом, что там, где размещена эта статья, идёт врезка следующего содержания:

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

Итак, в этом месте для лучшего понимания нужно прямо объяснить значение термина линейное программирование:
Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n-мерного пространства, задаваемых системами линейными уравнений и неравенств. Определение взято из поста @andron2303
А что такое экстремальная задача? Это задача на нахождение таких значений переменных, при которых какая-то функция (обычно называемая целевой функцией) принимает своё либо максимальное, либо минимальное значение. А максимальное или минимальное — это зависит от самой функции. В одних случаях это будет максимальное (как в нашей нынешней задаче), в других случаях мы можем пытаться минимизировать целевую функцию (например, если она соответствует штрафу или ошибке).

Таким образом, в выражении линейное программирование слово программирование гораздо ближе к такому значению слова "программа" как "программа партии, по обеспечению населения товарами народного потребления", чем к значению, "программа, как реализация какого-то алгоритма". В данном случае "программа" — это указание, сколько и какого топлива надо заправить.
Далее... А можно ли решать данную задачу с помощью ЭВМ? Да конечно можно... И для этого нужно описать алгоритм, который можно было бы запрограммировать. Можно ли сказать, что в статье такой алгоритм приводится? С натяжкой. Да, алгоритм объясняется, но он ни в одном месте он не приведён полностью, от начала до конца, а как бы распределён по всей статье. И тут получается, что упоминание возможности решать задачу с помощью ЭВМ, которое было хорошей мотивацией — оно, к сожалению, может сбивать с толку.

Далее я переформулирую задачу и попробую проанализировать её с точки зрения школьника:
Есть два вида топлива: А7 и А10. Мы заправляем X₁ литров А7 и X₂ литров А10.
Целевая функция:
Ограничения:
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,ㅤㅤㅤㅤㅤㅤㅤ(5)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ ,

Результат решения задачи: X₁ = 3, X₂ = 2

Внимательный школьник может заметить, что решение, полученное с помощью симплекс-метода, полностью соответствует решению системы линейных уравнений
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ ,ㅤㅤㅤㅤㅤㅤㅤㅤ(11)
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ,

т.е. при решении СЛАУ (системы линейных алгебраических уравнений) возникают точно такие же корни, из-за чего у школьника, не знающего что такое симплекс-метод, может возникнуть некорректное понимание, что будто бы симплекс-метод — это просто способ решения СЛАУ с помощью ЭВМ.
Дальше — опаснее!

В части статьи, под названием "Помогают графики", автор приводит такую картинку (рис.6, 8)

и следующий провокационный текст: "Обратите внимание: точ­ка Е как раз отвечает наилучше­му, оптимальному решению. Случайно ли это?"

И тут мой внутренний математик хочет просто закричать: "Да, чёрт побери, случайно!". У данного симплекса (четырёхугольника OBEC), тот факт, что точка Е соответствует экстремуму целевой функции — случайность. Ведь, например, если бы топлива назывались не А7 и А10, а, например, А6 (плотностью 2 кг/л) и А11 (плотностью 3 кг/л), тогда оптимальным планом было бы залить 4 литра А11, пролетев 44 часа. И это была бы уже точка С на приведённом рисунке.

А если бы топлива назывались А9 (с плотностью 2 кг/л) и А8 (с плотностью 3 кг/л), тогда решением была бы точка B на приведённом рисунке... Т.е мы бы залили 5 литров топлива А9 и пролетели бы 45 часов.

Неслучайность точки Е в данном случае выражается только в том, что какая-то из вершин четырёхугольника ОВЕС обязана быть решением экстремальной задачи. Это вытекает из линейности целевой функции. Неформально это можно выразить так: вот мы взяли начальный план — точку O (когда X₁ и X₂ равны нулю) и дальше, если мы хотим что-то максимизировать или минимизировать — надо идти в какую-то сторону до упора (в сторону, в направлении которой целевая функция - время полёта - возрастает).
При этом, если мы упрёмся в ребро, тогда возможно два варианта:
1) мы упёрлись в ребро не под прямым углом — тогда можно продолжать скользить вдоль ребра, стараясь максимизировать продвижение в заданном направлении.
2) мы упёрлись в ребро под прямым углом — но в этом случае все точки ребра (включая вершины, ограничивающие его) — будут решением задачи.

На рисунке 9 я повторил картинку из оригинальной статьи, добавив зелёным цветом вектор OF. Этот вектор имеет координаты {3.5, 5}, т.е. он сонаправлен с вектором {7, 10}. Из рисунка видно, что угол OKE чуть-чуть больше 90 градусов. Т.е. если бы мы привязали ниточку к грузику и тащили бы его по направлению вектора OF, то когда грузик уперся бы в отрезок CE — он "скатился" бы в точку E.

При этом, если бы целевая функция соответствовала бы топливам А6 и А11, её вектор градиента был бы OG, и тогда грузик "скатился" бы в точку C. А если бы мы заправляли A9 и A8, тогда градиент целевой функции был бы сонаправлен с вектором OH и грузик "скатился" бы точку B.

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

Тут у внимательного школьника опять может возникнуть закономерный вопрос: если решение — одна из вершин четырёхугольника, тогда зачем городить какой-то там симплекс-метод? Ведь можно просто подставить каждую из этих вершин в целевую функцию и узнать, на какой из них достигается максимум! И этот школьник будет очень сильно прав. Именно так и можно поступить, когда мы имеем дело с задачей с двумя переменными и четырьмя ограничениями. Но когда переменных не две, а много и ограничений не 4, а тоже очень много, количество вершин может быть довольно велико. И перебирать их все — может оказаться делом весьма затруднительным даже для компьютера. Поэтому их перебирают по-умному. Выбирают одну вершину, находят ребро, при движении в направлении которого целевая функция возрастает, и двигаются вдоль этого ребра до следующей вершины. Потом находят следующее ребро и т.д, пока не упрутся в вершину, из которой движение по всем рёбрам ведёт только к убыванию целевой функции. Эта последняя вершина и является решением.

Как было бы лучше построить изложение решения данной задачи?

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

close all;
clear all;

% Целевая функция для случая заправки смесью топлив А7 и А10
target_7_10 = @(x1, x2) 7*x1+10*x2;

% Целевая функция для случая заправки смесью топлив А6 и А11
target_6_11 = @(x1, x2) 6*x1+11*x2;

% Целевая функция для случая заправки смесью топлив А9 и А8
target_9_8  = @(x1, x2) 9*x1+8*x2;

% Функция вычисления запаса по массе топлива
mass_margin = @(x1, x2) 12-2*x1 -3*x2;

% Функция вычисления запаса по объёму топлива
vol_margin  = @(x1, x2) 5 -  x1 -  x2;

% области проверяемых значений для X1 и X2
xx1 = (0:0.01:6);
xx2 = (0:0.01:6);

[x1 x2] = meshgrid(xx1, xx2);

% вычисляем запас по объёму
vol_margin_values = vol_margin(x1, x2);
% обнуляем все значения, в которых запас по объёму отрицательный
vol_margin_values(find(vol_margin_values < 0)) = NaN;

% вычисляем запас по массе
mass_margin_values = mass_margin(x1, x2);
% обнуляем все значения, в которых запас по массе отрицательный
mass_margin_values(find(mass_margin_values < 0)) = NaN;

% так выглядят наши ограничения ОДЗ для Х1 и Х2:
figure;
s1 = mesh(x1, x2, mass_margin_values); 
set(s1,'facealpha',0.5);
hold on; 
s2 = mesh(x1, x2, vol_margin_values);
set(s2,'facealpha', 0.5);
hold off;
xlabel('x1');
ylabel('x2');
zlabel('margin');

% расчитываем целевую функцию
values_target_7_10 = target_7_10(x1,x2);
% обнуляем целевую функцию там, где нет запаса по массе или по объёму
values_target_7_10(find(isnan(vol_margin_values))) = NaN;
values_target_7_10(find(isnan(mass_margin_values))) = NaN;

% общий вид целевой функции
figure; mesh(x1, x2, values_target_7_10);
xlabel('x1');
ylabel('x2');
zlabel('flight time');
view(30,40);
title('A7/A10 target function top view');

% теперь посмотрим на целевую функцию, так, чтоб понять, где оптимум X1
figure; mesh(x1, x2, values_target_7_10);
xlabel('x1');
ylabel('x2');
zlabel('flight time');
view(0,0);
title('x1 optimal value for A7 (when x2 is A10)');
grid minor;

% теперь посмотрим на целевую функцию, так, чтоб понять, где оптимум X2
figure; mesh(x1, x2, values_target_7_10);
xlabel('x1');
ylabel('x2');
zlabel('flight time');
view(90,0);
title('x2 optimal value for A10 (when x1 is A7)');
grid minor;

% теперь посмотрим как выглядит наш "симплекс" сверху:
figure; mesh(x1, x2, values_target_7_10);
xlabel('x1');
ylabel('x2');
zlabel('flight time');
view(0,90);
title('Shape of the simplex');
grid minor;

И получить вот такую визуализацию (рис. 9):

Этот рисунок наглядно изображает область допустимых значений X₁ и X₂. Вертикальная ось — запасы свободных объёма и массы. Область допустимых значений — это та область, в которую покрывают оба треугольника (соответствует четырёхугольнику OBEC на рисунках 6,8).

Следующий рисунок (рис 11) показывает форму "лоскутка" значений целевой функции если мы используем топлива А7 и А10:

Из рисунка не очень понятно, где находится оптимальное значение, т.к. он нарисован в изометрической проекции, поэтому повернём его так, чтоб стало понятно, какие оптимальные значения для X₁ и X₂ (рис 12 и 13) :

(на рисунках 12 и 13 наглядно видно, что заливание 4 литров А10 даёт меньшее значение времени полёта, чем когда мы заливаем 2 литра А10, доливая остатки ёмкости бака топливом А7 и видно, что максимум целевой функции достигается именно при X₂ = 2 и X₁ = 3.
А вот так выглядит "симплекс" сверху:

В качестве упражнения для школьников я бы оставил возможность найти графически оптимальный план при условиях, что на заправке есть:
а) топлива А6 и А11
б) топлива А8 и А9
В приведённом скрипте для этого уже всё есть.

После такого графического решения я бы объяснил школьникам, что в случае, когда переменных больше двух, мы будем иметь дело не с плоской, а с объёмной фигурой, и вот эта-то вот объёмная фигура и называется страшным словом симплекс. По сути, симплекс — это любой выпуклый многогранник в N-мерном пространстве. При N=2 многогранник превращается в многоугольник.
Количество граней у такого многогранника равно количеству накладываемых ограничений (а в двумерной ситуации вместо граней будут рёбра многоугольника).

Здесь внимательный школьник задал бы вопрос: но ведь у нас всего 2 ограничения, а сторон у многоугольника 4. Как же так? И я бы ему ответил, что на самом деле в данной задаче 4 ограничения. Просто 2 из них не озвучены в явном виде и предложил бы самому эти два дополнительных ограничения найти (правильный ответ — это ограничения ) и только после такого вот графического введения я бы может быть и предложил бы школьнику одно из описаний симплекс-метода из уже упомянутых выше (раз и два).

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

Теперь можно попробовать разобраться и в приведённых в оригинальной статье уравнениях (когда они сгруппированы — читать и разбираться в них должно быть легче):

4. И всё-таки, как решить данную задачу с помощью компьютера?

Я бы рекомендовал использовать какой-нибудь язык численного моделирования (Matlab, Octave, R, Python). Поскольку мне ближе Octave, я приведу пример для него.

octave:68> c = [7 10]';
octave:69> A = [1 1; 2 3];
octave:70> b = [5 12];
octave:71> [xopt fmax] = glpk(c, A, b);
octave:72> xopt
xopt =

   3.0000
   2.0000

octave:73> fmax
fmax = 41
octave:74>

5. Заключение

Здесь я должен ещё раз обратить внимание на то, что оригинальная статья — это шедевр, несмотря на указанные мной недостатки. Нормальный учитель математики, физики, информатики, химии вполне мог бы разобраться и объяснить метод детям. Ну и важно понимать, что в тех условиях 1985 года, когда не было возможности использовать , когда компьютеры были редкостью, когда никакого Octave или Python не было и в помине, а формат журнала не позволял растечься мыслею по древу, написать то, что было написано — это огромный шаг вперёд...