Решение транспортной задачи в векторной постановке в среде Maple

Содержание

Введение

Глава 1. Задача транспортного типа

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

§2. Пример решения транспортной задачи

§3. Транспортные задачи по различным критериям

§4. Решение транспортной задачи в MS Excel

Глава 2: Maple для транспортной задачи

§1. Введение в Maple

§2. Управляющие структуры ветвления Maple языка (if предложение)

§3. Программа решения транспортной задачи

§4. Транспортная задача в векторных координатах (Для двух матриц)

§5. Транспортная задача в векторных координатах (Для трёх матриц)

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

Приложения

Введение

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

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

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

Глава 1. Задача транспортного типа

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

Пусть имеется несколько поставщиков однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки - стоимость перевозки единицы продукции. Если какая - либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+?). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

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

Транспортные задачи бывают:

1) открытые m ? n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)

2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)

Метод потенциалов «работает» только для закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.

Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.

Закрытая транспортная задача формулируется как Задача Линейного Программирования (ЗЛП) следующего вида:

,

где

- запас i - го поставщика

- потребность j - го потребителя

- цена перевозки единицы продукции по коммуникациям (i, j)

(от i - го поставщика к j - му потребителю)

- объем перевозки продукции (неизвестный) по коммуникациям (i, j).

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

Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей переменной содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.

Вектор двойственных переменных Y = (,…,,,…,) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные ,,…, - потенциалы поставщиков; переменные ,…,- потенциалы потребителей.

Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем:

В полученной двойственной задаче n·m ограничений, соответствующих каждой переменной ТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:

.

Неизвестные потенциалы и (их общее количество равно m + n) могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже).

, для заполненных клеток (i, j) таблицы ТЗ.

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

Утверждение

Закрытая транспортная задача всегда разрешима.

Доказательство

Необходимо установить следующее:

а) ТЗ имеет хотя бы одно допустимое решение

б) Целевая функция ТЗ ограничена снизу

а) Проверим, что (M==) является допустимым решением закрытой ТЗ. Не отрицательность очевидна, т.к. >0, >0, М>0.

Подставим предъявленное решение в произвольное ограничение первой группы = = =M= и в ограничения второй группы = = =M=. Всем ограничениям ТЗ предъявленное решение удовлетворяет, и, следовательно, Является допустимым решением ТЗ.

б) Выберем - наименьшую цену перевозки. Заменим в целевой функции ТЗ все коэффициенты на . Тогда получим

.

Т.е. целевая функция ТЗ ограничена снизу константой .

§2. Пример решения транспортной задачи

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

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.

Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

	60	100	80
120	5	10	12
70	8	6	4
50	0	0	0

Клетка (i,j) таблицы соответствует коммуникации, связывающей i-го поставщика с j-м потребителем.

Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:

а)число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);

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

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j - номер потребителя).

ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из a_i и потребности bj.

x_ij = min{ a_i, bj }

ШАГ З. Уменьшим запас a_i и потребность bj на величину перевозки x_ij, т.е.

a_i = a_i - x_ij,

bj =bj -x_ij

ШАГ 4. При исчерпании запаса (a_i = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности (bj =0) запрещаем такие же клетки вj-ом столбце.

В случае одновременного исчерпания запасов потребностей (ai =bj = 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.

Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).

Способ минимальной стоимости.

	60	100	80
120	5	10	12
70	8	6	4
50	0	0 50	0

1.Клетки с минимальной ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем способе).

2 . x₃₂ = min{50,60} = 50

3. a ^'₃ =50-50=0, b ^'₂ = 100-50=50

4.Запрещаем строку 3.

	60	100	80
120	5	10	12
70	8	6	4 70
50	0	0 50	0

1.Клетка с min ценой ~ (2,3)

2.x₂₃ = min{70,80} = 70

3.a₂=70-70=0, b'₃ = 80-70=10

4.Запрещаем строку 2.

	60	100	80
120	5 60	10	12
70	8	6	4 70
50	0	0 50	0

1.Клетка с min ценой ~ (1,1)

2. x ₁₁=min{120,60} = 60

3.a _1' =120-60 = 60, b_1' = 0

4.В первом столбце запрещать уже нечего. Текущая таблица содержит две клетки (1,2) и (1,3).

	60	100	80
120	5 60	10 50	12
70	8	6	4 70
50	0	0 50	0

1.Выбираем клетку (1,2)

2.x ₁₂ =min{110,100} = 100

3.a ₁ =110-100 = 10, b^'₁ = 0

4.Текущая таблица содержит одну клетк((1,3).

	60	100	80
120	5 60	10 50	12 10
70	8	6	4 70
50	0	0 50	0

1. Выбираем последнюю клетку(1,3)

2. x₁₃=min{10,10} = 10

3. a₁^' = b₃ = 0

4.Таблица исчерпана. Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

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

(1) u_i +vj -c_ij ?0

которое выполняется для всех клеток таблицы. Неизвестные здесь величины u_i и vj (называемые потенциалами) определяются из условий

(2 )u_i + v_j = c_ij

Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС).

Заполненные клетки Уравнения

(1,1) u₁ + v₁ =5

(1,2) u₁ + v₂ =10

(1,3) u₁ + v₃ =12

(2,3) u₂ +v₃ =4

(3,2) u₃ +v₂ =0

Положим, например, неизвестное u ₁ равным 0 (через него можно из первых трех уравнений найти v₁, v₂ и v₃). Последовательно из них находим u _{2 ,} u _3.

Этот метод можно сформулировать в виде единой правилы:

Неизвестный потенциал находится вычитанием известного из цены перевозки в заполненной клетке

Применим это правило для определения u и v в нашем примере и получим:

u₁ =0, u₂ =-8, u₃ =-6

v₁ =5, v₂ =10, v₃ =12

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

(2,1) u₂+v₁-c₂₁=-8+5-8=-11<0

(2,2) u ₂ +v₂ -c₂₂=-8+10-6=-4<0

(3,1) u ₃ +v₁ -c₃₁=-10+ 5-0=-5<0

(3,3) u ₃ +v₃ -c₃₃=-10+12-0=2>0

Следовательно, условие оптимальности нарушено в клетке (3,3).

Имеющийся план перевозок можно улучшить.

Дадим описание заключительного шага алгоритма метода потенциалов.

ШАГ 3 Улучшение плана перевозок.

Улучшение плана происходит путем назначения перевозки и>0 в ту клетку (i , j) таблицы, в которой нарушилось условие оптимальности. Но назначение ненулевой перевозки нарушает условия баланса вывоза продукции от поставщика i (вывозит весь запас и еще плюси>0 ) и условия баланса привоза продукции к потребителю j (получает все что можно и еще плюс и > 0). Условия баланса восстанавливают путем уменьшения вывоза от i-поставщика к какому-то другому потребителю j (уменьшают на и перевозку в какой-то заполненной клетке (i , j) строки i). При этом нарушается баланс привоза продукции к потребителю j (получает на и меньше, чем ему требуется). Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т.д. до тех пор, пока цикл перемещения перевозок не замкнется на клетке, в которой нарушалось условие оптимальности. Продемонстрируем эти рассуждения на нашем примере.

	60	100	80
120	5 60	10 50	12 10
70	8	6	4 70
50	0	0 50	0 +и

	60	100	80
120	5 60	10 50+и	12 10-и
70	8	6	4 70
50	0	0 50-и	0 +и

	60	100	80
120	5 60	10 60	12 0
70	8	6	4 70
50	0	0 40	0 10

1. Оптимальность нарушена в клетке (3,3). Назначим в нее перевозку и>0 (+и означает, увеличение на и).

2.Нарушается баланс вывоза от поставщика 3 (вывозит 50+ и, а это больше его запаса!). Уменьшаем на и перевозку в заполненной клетке строки 3 (вне заполненной уменьшать нельзя, так как это приведет к отрицательной перевозке).

Рассмотрим те клетки цикла в которых уменьшаем на и перевозку и берём минимум из вычитаемых, у нас это min{10- и ,50- и }=10.

И данное число надо подставить в цикл

§3. Транспортные задачи по различным критериям

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

Ряд экономических задач легко сводимы к транспортной задаче.

· Усложненные задачи транспортного типа

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

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

3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту A_i Bj можно провести не более q единиц груза, то Bj-й столбец матрицы разбивается равным разности B1j и B2j. В первом столбце спрос принимается равным разности между действительным спросом bj и ограничением q: b1j= bj-q, во втором - равным ограничению q т.е. b2j=q. Затраты с_ij в обоих столбцах одинаковы и равны данным, но в первом столбце B1j, в клетке соответствующей ограничению i, вместо истинного тарифа с_ij ставится искусственно завышенный тариф M (клетка блокируется). Затем задача решается обычным способом.

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

· Транспортная задача по критерию времени

Иногда возникает ситуация, когда в условиях (ТЗ) необходимо минимизировать не стоимость перевозок, а время их выполнения (Срочные грузы, перевозки скоропортящихся продуктов, работа «скорой помощи» и т.д.)

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

· Задача о назначениях (Венгерский метод)

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

§4. Решение транспортной задачи в MS Excel

В качестве примера я рассмотрел транспортную задачу для 3 складов и 5 магазинов.

· В ячейки C5:C7 записал объемы продукции, имеющиеся на 3 складах.

· В ячейки E5:I5 - заявки на продукцию, поступившие от магазинов.

· В ячейки B10:F12 - матрицу транспортных расходов, задающую расходы на перевозку из I-го склада в J-й магазин единицы продукции.

· В ячейки B15:F17 - план перевозок - матрицу, задающую количество товара, перевезенного из I-го склада в J-й магазин. Начальное распределение плана задано по принципу "каждой сестре по серьге", равномерно распределив всю имеющуюся на складе продукцию по магазинам. Эти ячейки являются регулируемыми и Решатель должен найти более подходящее решение, изменив значения в этих ячейках.

· В ячейку D19 - записал целевую функцию:

{ =СУММПРОИЗВ(B10:F12;B15:F17) }

· В ячейки D21:H21 записал ограничения, задающие требование о точном выполнении заявки каждого магазина. Как обычно, я записал соответствующую формулу в первую из этих ячеек:

{ =СУММ(B15:B18) }

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

· Затем задал следующую группу ограничений. Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D22, имеет вид:

{ СУММ(B15:F15)}

Эта формула скопировать уже по столбцу D.

Подготовительный этап завершен - можно вызывать Решатель.

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

После выбора данной команды появится диалоговое окно.

Поскольку в качестве критерия оптимизации нами выбрана минимизация цены на грузоперевозки, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета общей цены грузоперевозки. В нашем случае это ячейка $D$19. Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;

В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($B$15:$F$17). Это означает, что для достижения минимальноq цены груз - перевозок будут меняться значения в ячейках B15 по F17, то есть будут изменяться количество груза, перевезенного по конкретному маршруту.

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

В группе полей Ограничения нажмите кнопку Добавить. Появится диалог Добавление ограничения.

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

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

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

Первое условие $С$4:$F$8>=0. Оно означает, что объем перевозок не может быть отрицательным, то есть, если на складе не хватает минеральных удобрений, их не везут с пункта доставки, на который эти минеральные удобрения были завезены ранее. Грузопоток имеет только одно направление - от складов к пунктам доставки удобрений.

Второе условие $D$21:$H$21 >=$E$5:$I$5.

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

И. наконец, третье, и последнее условие $D$22:$D$24<=$C$5:$C$7.

Оно означает, что значение в ячейке C5 должно быть меньше или равно значению в D22 т.д. В ячейках с D22 по D24 на листе находятся объемы поставок с конкретных складов. В ячейках с C5 по C7 - запасы на этих же складах. Так как невозможно вывести со склада больше, чем на нем есть, первое значение должно быть не больше второго.

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

После нахождения решения появляется диалог Результаты поиска решения

Глава 2. Maple для транспортной задачи

§1. Введение в Maple

Системы компьютерной алгебры (СКА) находят все более широкое применение во многих областях науки таких как: математика, физика, химия, информатика и т.д., техники, технологии, образовании и т.д. СКА типа Maple, Mathematica, MuPAD, Macsyma, Axiom, Reduce и Magma становятся все более популярны, и для решения задач преподавания математически ориентированных дисциплин, в научных исследованиях и промышленности. Данные системы являются мощными инструмента и для ученых, инженеров и педагогов. Исследования на основе СКА технологии, как правило, сочетают алгебраические методы с продвинутыми вычислительными методами. В это смысле СКА - междисциплинарная область между математикой и информатикой, в которой исследования сосредотачиваются как на разработке алгоритмов для символьных (алгебраических) вычислений и обработки на компьютерах, так и на создании языков программирования и программной среды для реализации подобных алгоритмов и базирующихся на них задач различного назначения.

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

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

Программирование в среде Maple языка в большинстве случаев не требует, какого то особого программистского навыка (хотя его наличие и весьма нелишне), т.к. в отличие от других языков универсального назначения и многих проблем, но ориентированных Maple язык включает большое число математически ориентированных функций и процедур, позволяя только одним вызовом решать достаточно сложные самостоятельные задачи, например: решать системы дифференциальных или алгебраических уравнений, находить минимакс выражения, вычислять производные и интегралы, выводить графики сложных функций и т.д. Интерактивность языка обеспечивает простоту его освоения и удобство редактирования и отладки, прикладных Maple документов и программ. Реальная же мощь Maple языка обеспечивается не только его управляющими и структурами и структурами данных, но и все богатство его функциональных (встроенных, библиотечных, модульных) и прикладных (Maple документов) средств, созданных к настоящему времени пользователя и из различных прикладных областей, прежде всего, математических. Важнейшим преимущество Maple является открытость его архитектуры, что позволило в кратчайшие сроки создать широки кругом пользователей из многих областей науки, образования, техники и т.д. обширных наборов процедур и модулей, которые значительно расширили как его возможности, так и сферу приложений. К их числу можно с полны основание отнести и представленную в библиотеку, содержащую более 700 средств, дополняющих средства пакета, устраняющих ряд его недоработок, расширяющих ряд его стандартных средств и повышающих уровень совместности релизов пакета.

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

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

§2. Управляющие структуры ветвления Maple языка (if предложение)

Достаточно сложные алгоритмы вычислений, обработки информации и/или управляющие (в первую очередь) не могут обойтись сугубо последовательной схемой, а включают различные конструкции, изменяющие последовательный порядок выполнения алгоритма в зависимости от наступления тех или иных условий: циклы, ветвления, условные и безусловные переходы (такие конструкции иногда называются управляющими). Для организации управляющих конструкций ветвящегося типа Maple язык располагает довольно эффективным средством, обеспечиваемые if предложением и имеющие следующие три формата кодирования:

(1)if <ЛУ >then <ПП >end if {;|}

(2)if <ЛУ >then <ПП1 >else <ПП2 >end if {;|}

(3)if <ЛУ1 >then <ПП1 >elif <ЛУ2 >then <ПП2 >else <ПП3 >end if {;|}

В качестве логического условия (ЛУ ) всех четырех форматов if предложения выступает любое допустимое булевское выражение, образованное на основе операторов отношения {<|<=|>|>=|=|<>}, логических операторов {and, or, not} и логических констант {true,false,FAIL}, и возвращающее логическое {true |false} значение. Последовательность предложений (ПП) представляет собой управляющую структуру типа следования, предложения которой завершаются {;|:} разделителе; для последнего предложения ПП кодирование разделителя необязательно. Во всех форматах, кроме последнего, ключевая фраза `end if` определяет закрывающую скобку (конец) if предложения и его отсутствие идентифицирует синтаксическую ошибку, вид которой определяется контексто if предложения. Каждому if слову должна строго со ответствовать своя скобка `end if`.

Первый формат if предложения несет следующую смысловую нагрузку: если результат вычисления ЛУ возвращает true значение, то выполняется указанная за ключевым then слово ПП, в противно случае выполняется следующее за if предложение, т.е. if предложение эквивалентно пустому предложению. При этом если if предложение завершается (;) разделителе, то выводятся результаты вычисления всех предложений образующих ПП, независимо от типа завершающего их {:|;} разделителя. Следовательно, во избежание вывода и возврата излишней промежуточной информации, завершать if предложение рекомендуется (:) разделителе.

Второй формат if предложения несет следующую смысловую нагрузку: если результат вычисления ЛУ возвращает true значение, то выполняется указанная за ключевым then слово ПП1, в противно случае выполняется следующая за ключевым else слова ПП2. Замечание относительно вывода промежуточных результатов для случая первого формата if предложения сохраняет силу и для второго формата кодирования.

Третий формат if предложения несет смысловую нагрузку, легко усматриваемую из следующей общей R функции, поясняющей принцип выбора выполняемой ПП в зависимости от цепочки истинности предшествующих ей ЛУ j (j =1 ..k) в предложении.

§3. Программа решения транспортной задачи

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

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

Алгоритм программы решения транспортной задачи:

1. вводим первоначальные данные задачи

2. описываем все переменные

3. подключение библиотеки simplex

4. находим оптимальный план перевозок

5. находим минимальное значение функции

§4. Транспортная задача в векторных координатах (Для двух матриц)

Постановка задачи

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

Алгоритм решения

1. Решить первую транспортную задачу, найдя цену перевозки и план перевозки.

2. Решить вторую транспортную задачу (с другими ценами), найдя цену перевозки и план перевозки.

3. Составляем матрицу M=, где f1x - это план перевозки первой задачи, поставленный в функцию цели первой задачи; f2x - это план перевозки первой задачи поставленный, в функцию цели второй задачи; f1y - это план перевозки второй задачи, поставленный в функцию цели первой задачи; f2y - это план перевозки второй задачи, поставленный в функцию цели второй задачи.

4. Матрицу M транспонируем. Полученную матрицу обозначаем A.

5. Находим собственные значения и собственные векторы матрицы А.

6. Берем один из столбцов матрицы собственных векторов, в зависимости конечно от собственных значений (если собственное значение равное единице стоит первым, то берем первый столбец, иначе второй ) и нормируем этот столбец.

7. Первую координату нормированного вектора умножаем на первую матрицу цен и складываем с второй матрицей цен умноженное на вторую координату полученного нормированного вектора. Получили новую матрицу цен.

8. Решаем новую транспортную задачу с таким же объемом поставок и потребностей, но с новыми ценами, полученными в пункте 7.

9. Новый план перевозок ставим в функцию цели первой и второй транспортной задачи и таким образом получаем УПРАВЛЕНИЯ. На содержательном уровне нашли оптимальное управление, что одновременно минимизирует стоимость и время перевозки.

Блок-схема



§5. Транспортная задача в векторных координатах (Для трёх матриц)

Постановка задачи

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

Алгоритм решения

1. Решить первую транспортную задачу, найдя цену перевозки и план перевозки.

2. Решить вторую транспортную задачу (с другими ценами), найдя цену перевозки и план перевозки.

3. Решить третью транспортную задачу (с другими ценами), найдя цену перевозки и план перевозки.

4. Составляем матрицу M=,

5. где f1x - это план перевозки первой задачи, поставленный в функцию цели первой задачи; f2x - это план перевозки первой задачи поставленный, в функцию цели второй задачи; f3x - это план перевозки первой задачи поставленный, в функцию цели третьей задачи; f1y - это план перевозки второй задачи, поставленный в функцию цели первой задачи; f2y - это план перевозки второй задачи, поставленный в функцию цели второй задачи; f3y - это план перевозки второй задачи, поставленный в функцию цели третьей задачи; f1v - это план перевозки третьей задачи, поставленный в функцию цели первой задачи; f2v - это план перевозки третьей задачи, поставленный в функцию цели второй задачи; f3v - это план перевозки третьей задачи, поставленный в функцию цели третьей задачи.

6. Матрицу M транспонируем. Полученную матрицу обозначаем A.

7. Находим собственные значения и собственные векторы матрицы А.

8. Берем один из столбцов матрицы собственных векторов, в зависимости конечно от собственных значений (если собственное значение равное единице стоит первым, то берем первый столбец, иначе второй, а если и не второй, то третий) и нормируем этот столбец.

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

10. Решаем новую транспортную задачу с таким же объемом поставок и потребностей, но с новыми ценами, полученными в пункте 8.

11. Новый план перевозок ставим в функцию цели первой, второй и третьей транспортной задачи и таким образом получаем УПРАВЛЕНИЯ. На содержательном уровне требуется найти оптимальное управление, что одновременно минимизирует стоимость, время и обратная функция качества перевозки.

Блок-схема



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

1. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1993.

2. Аладьев В.З., Богдявичюс М.А. MAPLE 6: Решение математических, статистических и физико-технических задач - М.: Лаборатория Базовых Знаний, 2001.

3. Бережная Е.В., Бережной В.И. математические методы моделирования экономических систем. М.: Мир, 1977.

4. Воробьёв Н.Н. Основы теории игр. Бескоалиционные игры. М.: Наука, 1984.

5. Канторович Л.В. Математические методы в организации и планировании производства. Ленинград: Изд. - во ЛГУ, 1939.

6. Карлин С. Математические методы в теории игр программировании и экономике. М: Мир, 1964.

7. Матвеев В.А. Уточнённое по конусу решение многокритериальной задачи. // Вестник НовГУ. Серия : Технические науки. 2006. № 39. C .23 - 27.

8. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.:ВШ, Книжный дом Университет, 1998.

Приложение 1

Листинг программы решения транспортной задачи

> restart:

> a1:=[1,2,3,4,5,6,7,8,9,10]; a2:=[11,12,13,14,15,16,17,18,19,20]; a3:=[21,22,23,24,25,26,27,28,29,30]; a4:=[31,32,33,34,35,36,37,38,39,40]; a5:=[41,42,43,44,45,46,47,48,49,50]; a6:=[51,52,53,54,55,56,57,58,59,60]; a7:=[61,62,63,64,65,66,67,68,69,70]; a8:=[71,72,73,74,75,76,77,78,79,80]; a9:=[81,82,83,84,85,86,87,88,89,90]; a10:=[91,92,93,94,95,96,97,98,99,100]; b:=[25,30,35,40,45,50,55,60,65,70]; c:=[50,45,40,35,30,25,55,60,65,70];

(вводим первоначальные данные задачи)

a1 := [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

a2 := [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

a3 := [21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

a4 := [31, 32, 33, 34, 35, 36, 37, 38, 39, 40]

a5 := [41, 42, 43, 44, 45, 46, 47, 48, 49, 50]

a6 := [51, 52, 53, 54, 55, 56, 57, 58, 59, 60]

a7 := [61, 62, 63, 64, 65, 66, 67, 68, 69, 70]

a8 := [71, 72, 73, 74, 75, 76, 77, 78, 79, 80]

a9 := [81, 82, 83, 84, 85, 86, 87, 88, 89, 90]

a10 := [91, 92, 93, 94, 95, 96, 97, 98, 99, 100]

b := [25, 30, 35, 40, 45, 50, 55, 60, 65, 70]

c := [50, 45, 40, 35, 30, 25, 55, 60, 65, 70]

> proc(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,b,c) (означает начало процедуры)

>f,x11,x12,x13,x14,x15,x16,x17,x18,x19,x110,x21,x22,x23,x24,x25,x26,x27,x28,x29,x210,x31,x32,x33,x34,x35,x36,x37,x38,x39,x310,x41,x42,x43,x44,x45,x46,x47,x48,x49,x410,x51,x52,x53,x54,x55,x56,x57,x58,x59,x510, x61,x62,x63,x64,x65,x66,x67,x68,x69,x610, x71,x72,x73,x74,x75,x76,x77,x78,x79,x710, x81,x82,x83,x84,x85,x86,x87,x88,x89,x810, x91,x92,x93,x94,x95,x96,x97,x98,x99,x910, x101,x102,x103,x104,x105,x106,x107,x108,x109,x1010; (описываем все переменные)

Warning, premature end of input

> with(simplex): (подключение библиотеки simplex)

Warning, the protected names maximize and minimize have been redefined and unprotected

>minimize(a1[1]*x11+a1[2]*x12+a1[3]*x13+a1[4]*x14+a1[5]*x15+a1[6]*x16+a1[7]*x17+a1[8]*x18+a1[9]*x19+a1[10]*x110+ a2[1]*x21+a2[2]*x22+a2[3]*x23+a2[4]*x24+a2[5]*x25+a2[6]*x26+a2[7]*x27+a2[8]*x28+a2[9]*x29+a2[10]*x210+ a3[1]*x31+a3[2]*x32+a3[3]*x33+a3[4]*x34+a3[5]*x35+a3[6]*x36+a3[7]*x37+a3[8]*x38+a3[9]*x39+a3[10]*x310+ a4[1]*x41+a4[2]*x42+a4[3]*x43+a4[4]*x44+a4[5]*x45+a4[6]*x46+a4[7]*x47+a4[8]*x48+a4[9]*x49+a4[10]*x410+ a5[1]*x51+a5[2]*x52+a5[3]*x53+a5[4]*x54+a5[5]*x55+a5[6]*x56+a5[7]*x57+a5[8]*x58+a5[9]*x59+a5[10]*x510+ a6[1]*x61+a6[2]*x62+a6[3]*x63+a6[4]*x64+a6[5]*x65+a6[6]*x66+a6[7]*x67+a6[8]*x68+a6[9]*x69+a6[10]*x610+ a7[1]*x71+a7[2]*x72+a7[3]*x73+a7[4]*x74+a7[5]*x75+a7[6]*x76+a7[7]*x77+a7[8]*x78+a7[9]*x79+a7[10]*x710+ a8[1]*x81+a8[2]*x82+a8[3]*x83+a8[4]*x84+a8[5]*x85+a8[6]*x86+a8[7]*x87+a8[8]*x88+a8[9]*x89+a8[10]*x810+ a9[1]*x91+a9[2]*x92+a9[3]*x93+a9[4]*x94+a9[5]*x95+a9[6]*x96+a9[7]*x97+a9[8]*x98+a9[9]*x99+a9[10]*x910+ a10[1]*x101+a10[2]*x102+a10[3]*x103+a10[4]*x104+a10[5]*x105+a10[6]*x106+a10[7]*x107+a10[8]*x108+a10[9]*x109+a10[10]*x1010,{x11+x12+x13+x14+x15+x16+x17+x18+x19+x110=b[1], x21+x22+x23+x24+x25+x26+x27+x28+x29+x210=b[2], x31+x32+x33+x34+x35+x36+x37+x38+x39+x310=b[3], x41+x42+x43+x44+x45+x46+x47+x48+x49+x410=b[4], x51+x52+x53+x54+x55+x56+x57+x58+x59+x510=b[5], x61+x62+x6+x64+x65+x66+x67+x68+x69+x610=b[6], x71+x72+x73+x74+x75+x76+x77+x78+x79+x710=b[7], x81+x82+x83+x84+x85+x86+x87+x88+x89+x810=b[8], x91+x92+x93+x94+x95+x96+x97+x98+x99+x910=b[9], x101+x102+x103+x104+x105+x106+x107+x108+x109+x1010=b[10], x11+x21+x31+x41+x51+x61+x71+x81+x91+x101=c[1], x12+x22+x32+x42+x52+x62+x72+x82+x92+x102=c[2], x13+x23+x33+x43+x53+x63+x73+x83+x93+x103=c[3], x14+x24+x34+x44+x54+x64+x74+x84+x94+x104=c[4], x15+x25+x35+x45+x55+x65+x75+x85+x95+x105=c[5], x16+x26+x36+x46+x56+x66+x76+x86+x96+x106=c[6], x17+x27+x37+x47+x57+x67+x77+x87+x97+x107=c[7], x18+x28+x38+x48+x58+x68+x78+x88+x98+x108=c[8], x19+x29+x39+x49+x59+x69+x79+x89+x99+x109=c[9], x110+x210+x310+x410+x510+x610+x710+x810+x910+x1010=c[10]}, NONNEGATIVE); (находим оптимальный план перевозок)

{x52 = 0, x53 = 0, x54 = 0, x55 = 0, x56 = 0, x57 = 0, x58 = 0, x59 = 0, x61 = 0, x62 = 0, x64 = 0, x65 = 0, x51 = 0, x41 = 0, x42 = 0, x43 = 0, x44 = 0, x45 = 0, x46 = 0, x47 = 0, x49 = 0, x36 = 0, x96 = 0, x97 = 0, x98 = 0, x99 = 0, x410 = 0, x34 = 0, x35 = 0, x37 = 0, x38 = 0, x39 = 0, x95 = 0, x78 = 0, x79 = 0, x81 = 0, x82 = 0, x83 = 0, x87 = 0, x88 = 0, x89 = 0, x91 = 0, x31 = 0, x11 = 0, x66 = 0, x71 = 0, x72 = 0, x73 = 0, x74 = 0, x75 = 0, x18 = 0, x21 = 0, x22 = 0, x23 = 0, x24 = 0, x25 = 0, x26 = 0, x27 = 0, x28 = 0, x12 = 0, x13 = 0, x14 = 0, x15 = 0, x16 = 0, x17 = 0, x92 = 15, x102 = 20, x48 = 40, x101 = 50, x69 = 10, x94 = 10, x84 = 25, x76 = 20, x77 = 35, x67 = 20, x85 = 30, x93 = 40, x29 = 30, x310 = 25, x32 = 10, x68 = 20, x105 = 0, x106 = 0, x107 = 0, x108 = 0, x109 = 0, x1010 = 0, x6 = 0, x33 = 0, x110 = 0, x210 = 0, x710 = 0, x810 = 0, x910 = 0, x610 = 0, x103 = 0, x104 = 0, x63 = 0, x510 = 45, x19 = 25, x86 = 5}

> assign(%); (присваивает переменные к функции)

>f:=a1[1]*x11+a1[2]*x12+a1[3]*x13+a1[4]*x14+a1[5]*x15+a1[6]*x16+a1[7]*x17+a1[8]*x18+a1[9]*x19+a1[10]*x110+ a2[1]*x21+a2[2]*x22+a2[3]*x23+a2[4]*x24+a2[5]*x25+a2[6]*x26+a2[7]*x27+a2[8]*x28+a2[9]*x29+a2[10]*x210+ a3[1]*x31+a3[2]*x32+a3[3]*x33+a3[4]*x34+a3[5]*x35+a3[6]*x36+a3[7]*x37+a3[8]*x38+a3[9]*x39+a3[10]*x310+ a4[1]*x41+a4[2]*x42+a4[3]*x43+a4[4]*x44+a4[5]*x45+a4[6]*x46+a4[7]*x47+a4[8]*x48+a4[9]*x49+a4[10]*x410+ a5[1]*x51+a5[2]*x52+a5[3]*x53+a5[4]*x54+a5[5]*x55+a5[6]*x56+a5[7]*x57+a5[8]*x58+a5[9]*x59+a5[10]*x510+ a6[1]*x61+a6[2]*x62+a6[3]*x63+a6[4]*x64+a6[5]*x65+a6[6]*x66+a6[7]*x67+a6[8]*x68+a6[9]*x69+a6[10]*x610+ a7[1]*x71+a7[2]*x72+a7[3]*x73+a7[4]*x74+a7[5]*x75+a7[6]*x76+a7[7]*x77+a7[8]*x78+a7[9]*x79+a7[10]*x710+ a8[1]*x81+a8[2]*x82+a8[3]*x83+a8[4]*x84+a8[5]*x85+a8[6]*x86+a8[7]*x87+a8[8]*x88+a8[9]*x89+a8[10]*x810+ a9[1]*x91+a9[2]*x92+a9[3]*x93+a9[4]*x94+a9[5]*x95+a9[6]*x96+a9[7]*x97+a9[8]*x98+a9[9]*x99+a9[10]*x910+ a10[1]*x101+a10[2]*x102+a10[3]*x103+a10[4]*x104+a10[5]*x105+a10[6]*x106+a10[7]*x107+a10[8]*x108+a10[9]*x109+a10[10]*x1010;

(нашли минимальное значение функции)

f := 28350

>[x11,x12,x13,x14,x15,x16,x17,x18,x19,x110];[x21,x22,x23,x24,x25,x26,x27,x28,x29,x210];[x31,x32,x33,x34,x35,x36,x37,x38,x39,x310];[x41,x42,x43,x44,x45,x46,x47,x48,x49,x410];[x51,x52,x53,x54,x55,x56,x57,x58,x59,x510]; [x61,x62,x63,x64,x65,x66,x67,x68,x69,x610]; [x71,x72,x73,x74,x75,x76,x77,x78,x79,x710]; [x81,x82,x83,x84,x85,x86,x87,x88,x89,x810]; [x91,x92,x93,x94,x95,x96,x97,x98,x99,x910]; [x101,x102,x103,x104,x105,x106,x107,x108,x109,x1010];f;

[0, 0, 0, 0, 0, 0, 0, 0, 25, 0]

[0, 0, 0, 0, 0, 0, 0, 0, 30, 0]

[0, 10, 0, 0, 0, 0, 0, 0, 0, 25]

[0, 0, 0, 0, 0, 0, 0, 40, 0, 0]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 45]

[0, 0, 0, 0, 0, 0, 20, 20, 10, 0]

[0, 0, 0, 0, 0, 20, 35, 0, 0, 0]

[0, 0, 0, 25, 30, 5, 0, 0, 0, 0]

[0, 15, 40, 10, 0, 0, 0, 0, 0, 0]

[50, 20, 0, 0, 0, 0, 0, 0, 0, 0]

28350

Приложение 2

Листинг программы решения транспортной задачи в векторных координатах (Для двух матриц)

> restart:

> b:=[50,18,12,80,15,15];

b := [50, 18, 12, 80, 15, 15]

> c:=[14,20,22,24,50,60];

c := [14, 20, 22, 24, 50, 60]

(Решить первую транспортную задачу, найдя цену перевозки и план перевозки)

>X:=Matrix(6,6,[[3,8,9,1,9,0],[3,4,5,0,9,6],[2,7,6,0,9,0],[9,1,9,4,7,2],[2,4,5,6,4,1],[1,4,5,7,8,7]]);

X := Matrix(6,6,{(1, 1) = 3, (1, 2) = 8, (1, 3) = 9, (1, 4) = 1, (1, 5) = 9, (2, 1) = 3, (2, 2) = 4, (2, 3) = 5, (2, 5) = 9, (2, 6) = 6, (3, 1) = 2, (3, 2) = 7, (3, 3) = 6, (3, 5) = 9, (4, 1) = 9, (4, 2) = 1, (4, 3) = 9, (4, 4) = 4, (4, 5) = 7, (4, 6) = 2, (5, 1) = 2, (5, 2) = 4, (5, 3) = 5, (5, 4) = 6, (5, 5) = 4, (5, 6) = 1, (6, 1) = 1, (6, 2) = 4, (6, 3) = 5, (6, 4) = 7, (6, 5) = 8, (6, 6) = 7},datatype = anything,storage = rectangular,order = Fortran_order,shape = [])

> proc(X,b,c)

>f1x,x11,x12,x13,x14,x15,x16,x21,x22,x23,x24,x25,x26,x31,x32,x33,x34,x35,x36,x41,x42,x43,x44,x45,x46,x51,x52,x53,x54,x55,x56,x61,x62,x63,x64,x65,x66;

Warning, premature end of input

> with(simplex):

Warning, the protected names maximize and minimize have been redefined and unprotected

>minimize(X[1,1]*x11+X[1,2]*x12+X[1,3]*x13+X[1,4]*x14+X[1,5]*x15+X[1,6]*x16+X[2,1]*x21+X[2,2]*x22+X[2,3]*x23+X[2,4]*x24+X[2,5]*x25+X[2,6]*x26+X[3,1]*x31+X[3,2]*x32+X[3,3]*x33+X[3,4]*x34+X[3,5]*x35+X[3,6]*x36+X[4,1]*x41+X[4,2]*x42+X[4,3]*x43+X[4,4]*x44+X[4,5]*x45+X[4,6]*x46+X[5,1]*x51+X[5,2]*x52+X[5,3]*x53+X[5,4]*x54+X[5,5]*x55+X[5,6]*x56+X[6,1]*x61+X[6,2]*x62+X[6,3]*x63+X[6,4]*x64+X[6,5]*x65+X[6,6]*x66, {x11+x12+x13+x14+x15+x16=b[1],x21+x22+x23+x24+x25+x26=b[2], x31+x32+x33+x34+x35+x36=b[3],x41+x42+x43+x44+x45+x46=b[4], x51+x52+x53+x54+x55+x56=b[5], x61+x62+x63+x64+x65+x66=b[6], x11+x21+x31+x41+x51+x61=c[1], x12+x22+x32+x42+x52+x62=c[2], x13+x23+x33+x43+x53+x63=c[3], x14+x24+x34+x44+x54+x64=c[4],x15+x25+x35+x45+x55+x65=c[5],x16+x26+x36+x46+x56+x66=c[6]},NONNEGATIVE);

{x11 = 0, x12 = 0, x13 = 0, x14 = 0, x15 = 0, x21 = 0, x22 = 0, x31 = 0, x32 = 0, x33 = 0, x36 = 0, x41 = 0, x51 = 0, x54 = 0, x55 = 0, x56 = 0, x64 = 0, x65 = 0, x66 = 0, x61 = 14, x16 = 50, x25 = 0, x26 = 0, x35 = 0, x43 = 0, x44 = 0, x52 = 0, x62 = 0, x34 = 12, x46 = 10, x24 = 12, x45 = 50, x63 = 1, x42 = 20, x23 = 6, x53 = 15}

> assign(%);

>f1x:=X[1,1]*x11+X[1,2]*x12+X[1,3]*x13+X[1,4]*x14+X[1,5]*x15+X[1,6]*x16+X[2,1]*x21+X[2,2]*x22+X[2,3]*x23+X[2,4]*x24+X[2,5]*x25+X[2,6]*x26+X[3,1]*x31+X[3,2]*x32+X[3,3]*x33+X[3,4]*x34+X[3,5]*x35+X[3,6]*x36+X[4,1]*x41+X[4,2]*x42+X[4,3]*x43+X[4,4]*x44+X[4,5]*x45+X[4,6]*x46+X[5,1]*x51+X[5,2]*x52+X[5,3]*x53+X[5,4]*x54+X[5,5]*x55+X[5,6]*x56+X[6,1]*x61+X[6,2]*x62+X[6,3]*x63+X[6,4]*x64+X[6,5]*x65+X[6,6]*x66;

f1x := 514

>[x11,x12,x13,x14,x15,x16];[x21,x22,x23,x24,x25,x26];[x31,x32,x33,x34,x35,x36];[x41,x42,x43,x44,x45,x46];[x51,x52,x53,x54,x55,x56];[x61,x62,x63,x64,x65,x66];f1x;