Адаптивное визуальное решение и его анализ в экономических задачах

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

Математическая модель этих задач имеет вид:

максимизировать (минимизировать) линейную функцию

при ограничениях m+2:

Алгоритм, в соответствии с которым решаются такие задачи, состоит в следующем:

1. Систему ограничений методом Жордана-Гаусса разрешают относительно m-базовых переменных, которые можно выбрать произвольно. Предположим, что в качестве базовых выбраны первые m-переменных .

Тогда система ограничений после преобразования будет иметь вид:

Её можно переписать в виде:

2. Разрешим систему относительно базовых переменных и подставим их в целевую функцию:

После приведения подобных целевая функция будет зависеть только от переменных xm+1, xm+2:

где величина S постоянная.

Отбрасывая базовые переменные переходим к неравенствам, содержащим только две переменные xm+1, xm+2, и в результате получаем следующую формулировку задачи.

Максимизировать (минимизировать) функцию

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

Решив эту задачу графически, найдём оптимальные значения и а используя их, находим оптимальные значения остальных переменных оптимального плана:

В качестве примера приведём решение графическим методом задачи оптимального раскроя.

Пример. Полосы листового проката длиной 200 см надо разрезать на заготовки А, Б и В длиной 57, 82 и 101 см для производства 50 изделий. На одно изделие требуется по 4 заготовки А и Б и 5 заготовок типа В. Известны способы (пять) раскроя одной полосы. Определить, какое количество полос проката нужно разрезать каждым способом для изготовления 50 изделий, чтобы отходы были наименьшими.

Величина отходов, количество заготовок того или иного вида приведены в табл. 5.1.

Таблица 5.1

Решение. Составим математическую модель задачи. Обозначим через xj количество полос, раскраиваемых по j-му способу . Для изготовления 50 изделий требуется заготовок:

типа А - 4 . 50 = 200 штук,

типа Б - 4 . 50 = 200 штук,

типа В - 5 . 50 = 250 штук.

Это позволит составить ограничения, если считать, что при получении заготовок использованы все способы раскроя.

Общее количество заготовок типа А равно

Общее количество заготовок типа Б равно

а заготовок типа В

Целевая функция определяется, если подсчитать общую величину отходов

Z = 29x1 + 4x2 + 42x3 + 36x4 + 17x5.

Итак, задача формулируется следующим образом:

Минимизировать функцию

Z = 29x1 + 4x2 + 42x3 + 36x4 + 17x5

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

xj 0, xj - целые.

Задача содержит пять переменных и три уравнения, т.е. относится к классу задач линейного программирования, которые можно решать графическим способом. В качестве базовых переменных возьмём переменные х3, х4 и х5 и методом Жордана-Гаусса разрешим ограничения относительно х3, х4 и х5. В квадратике выделен первый разрешающий элемент.

Таблица 5.2

Система ограничений после преобразования будет иметь вид

или

Подставляя выражения для базовых переменных в целевую функцию, отбрасывая х3, х4 и х5 в ограничениях, получаем следующую формулировку задачи относительно переменных х1, х2:

Для того чтобы, принимало минимальное значение необходимо

.

Далее решаем графически следующую задачу:

максимизировать функцию

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

.

Третье ограничение () выполняется при всех значениях , поэтому для задачи линейного программирования является лишним.

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

Результат решения задачи представлен на рис. 5.1.

Рис. 5.1

Значение целевой функции F = 11950 - 94 0 - 94 5 0 = 7250.

Исключение лишних неравенств легко выполнить графически лишь в 2-х и 3-х мерных пространствах. Для большего числа переменных необходимо применять изложенную ниже методику решения системы линейных неравенств.

6. Общая формула решений системы линейных неравенств

Вопрос о строении множества решений произвольной совместной системы неоднородных линейных неравенств

может быть сведен к поиску общей формулы решений системы однородных линейных неравенств

Действительно, если известна общая формула решений системы (6.2), то при из нее получаем решение для исходной системы (6.1). Поэтому основное внимание при анализе решений в дальнейшем уделено системе (6.2).

6.1 Определение фундаментальной системы решений для системы однородных линейных неравенств

Перепишем однородную систему в виде

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

в которой левая часть (до вертикальной черты) - единичная матрица E(1,1) n-й степени, а правая часть - транспонированная матрица (1,1) исходной матрицы A(1,1) системы (6.1.1).

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

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

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

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

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

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

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

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

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

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

Пример 6.1. Составить общую формулу неотрицательных решений для системы

В соответствии с изложенной вычислительной схемой переходим к новой системе однородных линейных неравенств

и составляем таблицу

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

Считая основным второй столбец таблицы , найдем её уравновешенные пары строк. Это будет одна пара (1,3). При этом таблица имеет вид

Считая основным столбцом таблицы третий столбец, получаем уравновешенные пары (1,2), (2,3) и новую таблицу

Считая последний столбец таблицы её основным столбцом, преобразуем её в таблицу

При этом уравновешенными в таблице были две пары строк (1,2), (1,3). Таблицей рассматриваемый процесс заканчивается.

Общая формула неотрицательных решений однородной системы принимает вид

Тогда для исходной системы решение можно записать в виде

Пример 6.2. Составить общую формулу неотрицательных решений для системы однородных линейных неравенств

сформированной из системы однородных линейных неравенств примера 6.1 путем добавления линейно зависимого пятого неравенства, полученного путем суммирования первого и второго ограничений с коэффициентами соответственно 1 и 5. Ниже приведены таблицы , основные столбцы и соответствующие уравновешенные пары строк,

Здесь основной столбец , уравновешенные строки - (1, 3);

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

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

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

7. Порядок выполнения работы

Перед выполнением лабораторной работы необходимо изучить теоретический материал (с. 3 - 16).

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

Имеем систему ограничений

и целевую функцию: .

Система ограничений может содержать лишние неравенства. Чтобы эти неравенства найти, необходимо построить область допустимых решений.

1. В плоскости X1OX2 строим область допустимых решений (ОДР). Получаем, что первое ограничение () окажется лишним.

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

Система ограничений после преобразований будет иметь вид

2. Осуществляем проверку на наличие лишних неравенств. Для этого перейдём к системе однородных линейных неравенств

В соответствии с вычислительно схемой приведенной в п. 6.1. для нахождения общей формулы неотрицательных решений составим таблицу :

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

В таблицу прежде всего переносится третья строка, так как она пересекает основной столбец по неположительному элементу (-150). Затем в таблицу вносятся строки равновесия всех уравновешенных допустимых пар. Вторая строка получается суммированием первой строки, умноженной на 50 и третьей строки. Третья строка получается суммированием второй строки, умноженной на 50 и третьей строки.

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

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

7.1 Простые числа

a. Число 1 имеет только один положительный делитель, именно 1. В этом отношении число 1 в ряде натуральных чисел стоит особо.

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

b. Наименьший отличный от единицы делитель целого, большего единицы, есть число простое.

с. Для составления таблицы простых чисел, не превосходящих данного N, существует простой способ, называемый решетом Эратосфена. Он состоит в нижеследующем.

Выписываем числа

1, 2,..., N. (7.1.1)

Первое большее единицы число этого ряда есть 2; оно делится только на 1 и на самого себя, следовательно, оно простое.

Вычеркнем из ряда (7.1.1) (как составные) все числа, кратные 2, кроме самого 2. Первое следующее за 2 невычеркнутое число будет 3; оно не делится на 2 (иначе оно оказалось бы вычеркнутым), следовательно, 3 делится только на 1 и на самого себя, а потому оно также будет простым.

Вычеркиваем из ряда (7.1.1) все числа, кратные 3, кроме самого 3. Первое следующее за 3 невычеркнутое число будет 5; оно не делится ни на 2, ни на 3 (иначе оно оказалось бы вычеркнутым). Следовательно, 5 делится только на 1 и на самого себя, а потому оно также будет простым.

И т.д.

Когда указанным способом уже вычеркнуты все числа, кратные простых, меньших простого p, то все невычеркнутые, меньшие p2 ,будут простыми. Действительно, всякое составное a, меньшее p2 нами уже вычеркнуто, как кратное его наименьшего простого делителя, который Отсюда следует:

1. Приступая к вычеркиванию кратных простого p, это вычеркивание следует начинать с p2.

2. Составление таблицы простых чисел N закончено, как только вычеркнуты все составные кратные простых, не превосходящих

Таблица простых чисел приведена в Приложении № 1.

Продолжаем преобразование. Считая основным столбцом таблицы второй столбец, получаем уравновешенные пары (1,2), (1,3) и новую таблицу

Таблицей рассматриваемый процесс заканчивается.

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

Общая формула неотрицательных решений однородной системы принимает вид

Тогда для исходной системы решение можно записать в виде

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

Теперь рассмотрим реализацию этой задачи на MS Excel.

3. Определение фундаментальной системы решений для системы однородных линейных неравенств на MS Excel.

3.1. Запустите MS Excel: Пуск | Программы | Microsoft Excel.

3.2. Введите в ячейку A1 название таблицы: T1, а в диапазон ячеек A2:F4 элементы таблицы T1.

3.3. В ячейку A5 введите название таблицы T2 .

3.4. Третья строка таблицы T1 переносится без изменений в таблицу T2 , для этого необходимо методом протягивания выделить диапазон A4:F4 и скопировать его содержимое в диапазон ячеек A6:F6.

3.5. Введите в ячейку A7 формулу =A2*50+A4. Скопируйте эту формулу во все ячейки (наведите указатель мыши на маркер заполнения в правом нижнем углу рамки ячейки A7. Нажмите левую кнопку мыши и перетащите этот маркер, чтобы рамка охватила диапазон ячеек B7:F7). Аналогично в ячейку A8 введите формулу =A3*50+A4 и скопируйте её. После этого ненулевой элемент (-150) столбца таблицы T2 (ячейка D6), возникшего из основного, заменяем на - 1, а элементы последнего неположительного столбца - нулями. Таблица T2 сформирована.

3.6. В ячейку A9 введите название таблицы T3 .

3.7. Вторую и третью строки таблицы T2 перепишите в таблицу T3 .

3.8. В ячейку A12 введите формулу =A6*2+A7. Используйте метод автозаполнения, чтобы скопировать эту формулу во все ячейки диапазона A12:F12. Аналогично в ячейку A13 введите формулу =A6+A8 и скопируйте её. Ненулевые элементы столбца таблицы T3, возникшего из основного, заменяем на - 1. Таблица T3 сформирована.

Результаты проведенных преобразований приведены на рис. 7.1:

Рис. 7.1

4. Задание масштаба рисунка.

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

К подобным вычислительным проблемам может привести и наличие в неравенствах слишком малых по величине коэффициентов. В этом случае также применяется масштабирование коэффициентов, но уже в сторону их увеличения [1].

Таким образом, для визуализации решения зададим масштаб рисунка.

из первого уравнения ; из первого уравнения

Чтобы уложиться в масштаб необходимо уменьшить переменные. Например, примем и (числа могут быть произвольными, определяемые возможностями визуализации данных для вашего устройства вывода). Тогда коэффициент будет 50/5 = 10.

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

.

Тогда в новых обозначениях будем иметь:

5. Нахождение решения системы ограничений графическим способом с помощью программы lp_grafn.exe (программа разработана инж. Труновым Р.А.).

После запуска программы lp_grafn.exe на экране появится диалоговое меню программы, которое имеет следующие пункты:

- Выполнение по заданному варианту;

- Выполнение с вводом данных;

- Выход.

Необходимо выбрать второй пункт “Выполнение с вводом данных”. Перемещение по пунктам меню осуществляется кнопками <>, <>, а выбор - <Enter>.

После выбора соответствующего пункта появляется диалоговое окно, где необходимо ввести число ограничений (не более 7) и выбрать цель обработки ЦФ (0 - для минимизации и 1 - для максимизации функции).

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

<> - выбор прямой-ограничения (по часовой стрелке);

<> - выбор прямой-ограничения (против часовой стрелке);

<> - увеличение значения правой части ограничения в соответствии с установленным шагом;

<> - уменьшение значения правой части ограничения в соответствии с установленным шагом;

<Enter> - восстановление исходных (начальных) ограничений.

Назначение других функциональных клавиш, а также дополнительные возможности программы можно посмотреть по нажатию клавиши <F1>.

Выход из режима просмотра результата осуществляется по нажатию клавиши <Esc>.

Графическое решение с учётом масштабного коэффициента (k=10) приведено на рис. 7.2.

Рис. 7.2

С учётом масштабного коэффициента решение находится в точке (0, 50).

Значение целевой функции: F = 11950 - 94 0 - 94 50 = 11950 - 4700 = 7250.

6. Определение графического решения задачи.

Решение задачи находится путем совместного решения двух уравнений: .Решение удобно проводить с помощью программы MS Excel.

6.1. Запустите MS Excel: Пуск | Программы | Microsoft Excel.

6.2. Введите в диапазон ячеек A1:B2 элементы матрицы .

6.3. Заранее сформируем правую часть: в ячейках С1 и С2 вводим значения 150 и 0 соответственно.

6.4. Выделяем место для обратной матрицы. Это будет диапазон ячеек D1:E2. Щёлкните на кнопке Вставка функции панели инструментов Стандартная. В появившемся диалоговом окне в списке Категория выберите пункт Математические. А в списке Функция выберите функцию МОБР с параметрами A1:B2 (массив данных). Затем нажмите клавишу <F2>, а затем комбинацию клавиш <Ctrl+Shift+Enter>.

6.5. Выделите ячейки С4:C5 для нахождения координат точки оптимума. Аналогично предыдущему пункту выберите функцию МУМНОЖ с параметрами D1:E2 (обратная матрица) и С1:C2 (массив правых частей ограничений).

6.6. Находим целевую функцию. Для этого в ячейки A7 и B7 вводим коэффициенты целевой функции, а в ячейку С7 формулу =МУМНОЖ(A7:B7;C4:C5). В ячейку C8 вводим формулу = 11950 - C7 и получаем значение целевой функции 7250.

7. Построение ОДР на MS Excel для большого числа ограничений.

7.1. Запустите MS Excel: Пуск | Программы | Microsoft Excel.

7.2. В ячейки A1, A2 задайте текстовые переменные x1 и x2, а в ячейки B1, B2 введите нулевые их значения.

7.3. Аналогично в диапазон ячеек A3:A7 введите текстовые переменные f1:f5, а в ячейки B3:B7 линейные неравенства. Для примера система ограничений имеет вид:

B3=B1<=3;

B4=B2<=3;

B5=B1>=1;

B6=B2>=1;

B7=B1+B2<3.

7.4. Формируем функцию F, принимающую значений истина, если все неравенства выполняются, и ложь, если хотя бы одно из неравенств не выполняется. Для этого в ячейку D1 вводим логическую функцию И: D1=И(B3;B4;B5;B6;B7). Переменная D1 принимаем значение истина и ложь.

7.5. Формируем функцию F1. Текстовая переменная F1 заносится в ячейку С1, а сама переменная - в D2.

Функция F1 зависит от двух переменных x1, x2. Для её представления требуется двухмерная матрица. Для сокращения её объема заменим значения: ИСТИНА - на 1, ЛОЖЬ - на 0: D2 = ЕСЛИ(D1;1;0).

7.5. Для формирования матрицы D2 (x1, x2) вводим в ячейку С8=D2. В той же строке (см. рис. 7.3) вводится значение x1 из диапазона области работоспособности. В том же столбце, где находится C8 вводится значение x2 из диапазона области работоспособности.

Рис. 7.3

7.6. Выбираем пункт Данные | Таблица подстановки, предварительно выделив диапазон С8:K21. Множество единиц в этой матрице определяет ОДР. Для наглядности удобно произвести условное форматирование (Формат | Условное форматирование), изменив цвет единиц.

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

8. Варианты заданий

Вариант 1. Цех выпускает изделия двух видов: валы и втулки. На производство одного вала рабочий тратит 3 ч, одной втулки - 2 ч. От реализации вала предприятие получает прибыль 80 к., а от реализации втулки - 60 коп. Цех должен выпустить не менее 100 штук валов и не менее 200 штук втулок. Сколько валов и втулок должен выпустить цех, чтобы получить наибольшую сумму прибыли, если фонд рабочего времени производственных рабочих составляет 900 чел.-ч.?

Решение. Введём обозначения: x1 - количество валов, x2 - количество втулок.

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

и запишем целевую функцию

Далее необходимо провести проверку на наличие лишних неравенств.

Система ограничений после преобразований будет иметь вид

Строим матрицу :

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

В таблицу прежде всего переносится 3-я строка, так как она пересекается с основным столбцом по неположительному элементу (-900). Вторая строка получается суммированием 1-й строки, помноженной на 300 и 3-й строки. Третья строка получается суммированием 2-й строки, помноженной на 450 и 3-й строки.

Считая основным второй столбец таблицы , найдём её уравновешенные пары строк. Это будут пары (1,2) и (2,3).

В таблицу прежде всего переносится 2-я строка, так как она пересекается с основным столбцом по неположительному элементу (-200). Другие две строки таблицы получаются комбинированием пар строк (1,2) и (2,3) с такими коэффициентами, чтобы получился нуль на месте, определяемом основным столбцом.

Считая последний столбец таблицы её основным столбцом (уравновешенными при этом окажутся пары строк (1,3) и (2,3)), преобразуем её в таблицу

Таблицей рассматриваемый процесс заканчивается. Лишних неравенств не будет.

Далее для визуализации решения, необходимо задать масштаб рисунка.

из первого уравнения ; из первого уравнения

из второго уравнения ; из третьего уравнения

Чтобы уложиться в масштаб необходимо уменьшить переменные. Например, примем и (числа могут быть произвольными, определяемые возможностями визуализации данных для вашего устройства вывода). Тогда коэффициент будет 450/50 = 9. Для удобства счёта возьмём коэффициент равный 10.

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

.

Тогда в новых обозначениях будем иметь:

Найдём решение этой системы ограничений графическим способом (например, с помощью программы lp_grafn.exe).

Рис. 8.1

Из графика видно, что оптимальное решение находится в точке , а

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

Вариант 2. Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А составляет 10 руб., детали В - 16 р. Исходные данные для решении задачи представлены в таблице.

Определить производственную программу, максимизирующую прибыль при условии: деталей А произвести не менее 300 ед., а деталей В не более 200 ед.

Решение. Введём обозначения: x1 - количество деталей А, x2 - количество деталей В.

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

и запишем целевую функцию

Проводим проверку на наличие лишних неравенств. Система ограничений после преобразований будет иметь вид

Строим матрицу :

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

Считая основным второй столбец таблицы , нейдём её уравновешенные пары строк. Это будет одна пара (2,3). Таблица имеет вид

Считая основным столбцом таблицы третий столбец, получаем уравновешенные пары (1,2) и (2,3) и новую таблицу

Получаем, что 4-й и 5-й столбцы содержат нули и отрицательные элементы их необходимо исключить.

Общая формула неотрицательных решений однородной системы принимает вид

Тогда для исходной системы решение можно записать в виде

Таким образом, найдём решение системы ограничений, состоящей только из трёх ограничений графическим способом (рис. 8.2).

из первого уравнения ; из второго уравнения

из третьего уравнения ; из третьего уравнения

Чтобы уложиться в масштаб необходимо сократить переменные. Зададим, например,

что x1 должен укладываться в пределах от 1 до5 (k = 100), т.к. 500/5=100

x2 должен укладываться в пределах от 1 до 2 (k = 100), т.к. 200/2=100

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

Рис. 8.2

Оптимальное решение находится в точке , а

Тогда с учётом масштабного коэффициента k =100: , а . Таким образом, для получения максимальной прибыли от реализации деталей А и В необходимо произвести 400 ед. деталей А и 200 ед. деталей В.

Вариант 3. Потребность народного хозяйства в азотных удобрениях составляет 10 млн.т (100%). Её можно удовлетворить за счет производства двух продуктов: аммиачной селитры и аммиачной воды. Для производства необходим аммиак, общий расход которого для удовлетворения соответствующих нужд в плановом году не может превысить 8 млн. р. Технологические нормы материальных затрат, удельные текущие расходы и капитальные вложения в производство каждого из продуктов даны в таблице.

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

Решение. Пусть x1 - аммиачная селитра (в тоннах), x2 - аммиачная вода (в тоннах). Тогда из условия задачи можно составить следующие ограничения:

где коэффициент перед x1 во втором ограничении характеризует удельные затраты на производство аммиачной селитры, а коэффициент перед x2 - удельные затраты на производство аммиачной воды.

и целевую функцию, которая определяет наименьшие суммарные затраты:

Далее проводим проверку на наличие лишних неравенств. Система ограничений после преобразований будет иметь вид

Строим матрицу :

За основной примем первый столбец. Уравновешенными при этом оказываются пары строк (1,3) и (2,3). Тогда таблица преобразуется в новую таблицу

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

из первого уравнения ; из первого уравнения

из второго уравнения ; из второго уравнения

Зададим, например, что x1 должен укладываться в пределах от 1 до 4 (k = 106), x2 должен укладываться в пределах от 1 до 2 (k = 106). Тогда , а .

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

Графическое решение имеет вид:

Рис. 8.3

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

Вариант 4. При продаже двух видов товаров (А и В) торговое предприятие использует четыре вида ресурсов. Нормы затрат ресурсов на реализацию 1 ед. товара, объем ресурсов приведены в таблице. Доход от реализации 1 ед. товара А составляет 2 р., товара В - 3 р.

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

Решение. Введем обозначение: x1 - товар вида А, x2 - товар типа В. По условиям задачи составим систему ограничений

и целевую функцию, которая определяет максимальную прибыль предприятия:

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

Принципиально необходим перебор всех вариантов, но для упрощения проверим всего 1 вариант, когда предполагаемое неравенство будет лишним.

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

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

Строим таблицу :

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

Считая основным второй столбец таблицы , нейдём её уравновешенные пары строк. Это будут пары строк (1,2) и (2,3). Таблица имеет вид

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

Считая основным столбцом таблицы третий столбец, получаем уравновешенные пары (1,2) и (2,4) и новую таблицу:

.

Таблицей рассматриваемый процесс заканчивается.

Ввод масштабного коэффициента для данной задачи не требуется.

Графическое решение системы, состоящей только из трех ограничений

представлено на рис. 8.4.

Рис. 8.4

Так как решение находится в точке , , то оптимальный план реализации товаров А и В, обеспечивающие торговому предприятию максимальную прибыль составляет: 4 ед. товара А и 2 ед. товара В.

Вариант 5. Торговая организация планирует реализацию по двум товарным группам, по которым соответственно выделены фонды 80 тыс. и 50 тыс. руб. Уровень транспортных издержек составляет по этим товарам соответственно 1 и 2 %, уровень издержек, связанных с хранением товаров, - 2 и 1 %, уровень прибыли - 3 и 2 %. Предельные допустимые расходы, связанные с перевозкой и хранением товаров, равны 2,5 тыс. и 2,9 тыс. р. С учетом закупки товаров сверх выделенных фондов определить оптимальную структуру товарооборота, обеспечивающую торговой организации максимальную прибыль.

Решение. Введем обозначение: x1 - 1 товарная группа, x2 - 2 товарная группа. Тогда уровни издержек по этим товарам составят соответственно

уровень транспортных издержек и ;

уровень издержек, связанных с хранением и ;

уровень прибыли и .

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

- расходы, связанные с перевозкой;

- расходы на хранение;

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

и составим таблицу :

За основной примем первый столбец, уравновешенными будут пары (1,3) и (2,3). Таблица :

Считая последний столбец таблицы основным, найдём его уравновешенные пары строк. Это будут пары - (1,2), (2,3).

Таким образом, лишних неравенств нет.

Далее для визуализации решения зададим масштаб рисунка.

из первого уравнения ; из первого уравнения

из второго уравнения ; из третьего уравнения

Чтобы уложиться в масштаб необходимо уменьшить переменные. Для удобства счёта примем, например, что коэффициент равен , тогда и

С учётом новых переменных получаем систему ограничений и целевую функцию

Графическое решение задачи приведено на рис. 8.5.

Рис. 8.5

Оптимальное решение с учётом масштабного коэффициента находится в точке (,0).

Вариант 6. В суточный рацион включается два продукта питания Р1 и Р2 (см. табл.), причем Р1 должно войти в дневной рацион не более 200 ед. Стоимость 1 ед. продукта Р1 составляет 0,2 к., продукта Р2 - 0,4 к. Определить оптимальный рацион, стоимость которого будет наименьшей.

Решение. Введем обозначение: x1 - продукт питания Р1, x2 - продукт питания Р2.

На основе задания можно оставить систему ограничений

и записать целевую функцию .

По переменной x2 нет ограничений, поэтому для построения области допустимых решений необходимо ввести дополнительное ограничение. Вводим ограничение (отметим, что ограничение вводиться с большим запасом).

Для проверки на наличие лишних неравенств, проверяемое неравенство ставим последним и таким образом имеем:

Переходим к новой системе однородных линейных неравенств

и по этой системе строим таблицу :

Первый столбец правой части примем за основной. Уравновешенной при этом оказывается пара строк (1,3). Тогда таблица преобразуется в новую таблицу

Считая основным второй столбец таблицы , получаем уравновешенные пары (1,2), (2,3) и новую таблицу

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

Считая третий столбец таблицы её основным столбцом, преобразуем её в таблицу

При этом уравновешенными в таблице были две пары строк (1,2), (1,3).

Таким образом, графическое решение находим для системы только из 3-х ограничений (рис. 8.6)

Для визуализации решения зададим масштаб рисунка.

из первого уравнения ; из второго уравнения

из второго уравнения ; из третьего уравнения

Зададим, например, что x1 должен укладываться в пределах от 1 до 4 (k = 100), x2 должен укладываться в пределах от 1 до 10 (k = 100). Тогда и

С учётом новых переменных получаем систему ограничений и целевую функцию

Рис. 8.6

Оптимальный рацион таков: 200 ед. продукта Р1 и 400 ед. продукта Р2.

Вариант 7. Требуется составить суточный рацион для откорма свиней минимальной себестоимости (причем в рацион должно быть включено не более 2,5 кг ячменя). Кормовых единиц в сутки потребляется минимум 2,4 кг, протеина - 200 г. Исходные данные для решения задачи приведены в таблице.

Решение: Введем обозначения: x1 - количество комбикорма (кг), x2 - количество ячменя (кг).

Система ограничений и целевая функция имеют вид

По переменной x1 нет ограничений, поэтому для построения области допустимых решений необходимо ввести дополнительное ограничение. Вводим ограничение (ограничение вводиться с небольшим запасом).

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

Переходим к новой системе однородных линейных неравенств

и по этой системе строим таблицу :

Считая основным первый столбец таблицы , найдём её уравновешенные пары строк. Это будет одна пара (2,3). При этом таблица имеет вид

Считая основным столбцом таблицы второй столбец, получаем уравновешенные пары (1,2), (2,3) и новую таблицу :

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

В таблице за основной можно принять третий столбец. Уравновешенными при этом окажутся пары строк - (1,2) и (1,3). Таблица преобразуется в новую таблицу :

.

Таблицей рассматриваемый процесс заканчивается.

Масштабирование не требуется.

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

Графическое решение имеет вид, представленный на рис. 8.7.

Рис. 8.7

Оптимальное решение находится в точке , а .

Вариант 8. Хозяйство располагает следующими производственными ресурсами: площадь пашни составляет 600 га, количество чел.-дней конно-ручного труда - 4000. В таблице содержится информация о данном хозяйстве. Определить наиболее эффективное сочетание зерновых и кормовых культур при условии, что под кормовые культуры должно быть занято не менее 100 га пашни.

Решение. Введем обозначения: x1 - площадь пашни под зерновую культуру, x2 - площадь пашни под кормовую культуру.

Система ограничений и целевая функция по условию задачи имеет вид:

Переходим к новой системе однородных линейных неравенств

Строим таблицу :

Первый столбец можно принять за основной. Уравновешенными при этом оказываются пары строк (1,3), (2,3). Таблица будет иметь вид

Считая основным второй столбец таблицы , найдём её уравновешенные пары строк. Это будут пары строк (1,3) и (2,3). Таблица :

Считая основным столбцом таблицы третий столбец, получаем уравновешенные пары (1,2) и (1,3) и новую таблицу

Таким образом, лишних неравенств нет.

Для визуализации решения зададим масштаб рисунка.

Зададим, например, что x1 должен укладываться в пределах от 1 до 8, x2 должен укладываться в пределах от 1 до 6. Для удобства счёта примем, например, что коэффициент равен , тогда и

С учётом новых переменных получаем систему ограничений и целевую функцию

Графическое решение представлено на рис. 8.8:

Рис. 8.8

Наиболее эффективное сочетание зерновых и кормовых культур составляет: 400 га пашни под зерновую культуру, 200 га пашни под кормовую культуру.

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

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

Решение. Введём следующие обозначения: x1 - количество столов, x2 - количество шкафов.

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

и запишем целевую функцию .

Далее необходимо провести проверку на наличие лишних неравенств. Для этого переходим к новой системе однородных линейных неравенств

и составляем таблицу

Здесь первый столбец - основной, уравновешенные строки - (1,3), (2,3).

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

Так как нас интересует только наличие лишних неравенств, то на этом этапе процесс можно завершить. Лишних неравенств не будет.

Для получения наглядного графического решения введём масштабный коэффициент, равный 100. Тогда и .

В новых обозначениях будем иметь:

Решение этой системы ограничений графическим способом имеет вид (рис. 8.9):

Рис. 8.9

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

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

Решение. Пусть x1 - количество изделий вида А, а x2 - количество изделий вида В.

По условию задачи составим систему ограничений и запишем целевую функцию

Для проверки на лишние неравенства перейдём к новой системе ограничений

где лишнее (в данном случае 2-е неравенство) ставиться последним.

Строим матрицу :

За основной примем первый столбец правой части матрицы . Уравновешенными при этом окажутся пары строк (1,3) и (2,3).

В таблицу прежде всего переносится 3-я строка, так как она пересекается с основным столбцом по неположительному элементу (-168). Вторая строка получается суммированием 1-й строки, помноженной на 84 и 3-й строки помноженной на 5. Третья строка получается суммированием 2-й строки, помноженной на 21 и 3-й строки.

Считая основным второй столбец таблицы , найдём её уравновешенные пары строк. Это будут пары (1,3) и (2,3). В таблицу переносятся первые две строки, вторая строка получается суммированием 1-й строки, умноженной на 3 и 3-й строки, умноженной на 4, а третья строка - суммированием второй строки и 3-й, умноженной на 2.

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

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

Рис. 8.10

Оптимальное решение находится в точке (12, 6). Таким образом для обеспечения максимальной прибыли от реализации, необходимо выпускать 12 шт. изделий А и 6 шт. изделий В.

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

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