Применение методов линейного программирования

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

Z-0 = 3X₁ + 7X₂ + 2X₃

           

                                          

  X₁, X₂, X₃ ≥ 0.

4X₁+2X₂ ≤ 19

  X₂ + X₃ = 8

  X₁+2X₂ ≤24 

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

                                 Z-0 = 3X₁ + 7X₂ + 2X₃ → max

Ввел дополнительные переменные X₄, X₅. Ввел искусственную переменную R₁. 

Ограничения:

     3. Построил математическую модель задачи;

4X₁+2X₂ + X₄ = 19

  X₂ +  X₃ + R₁  = 8 

  X₁+2X₂ + X₅ = 24

     4. Выбрал метод решения  задачи и привел задачу к каноническому виду;

X_i≥0 ;    0-Z= -3X_1- -7X_2- -2X₃    
 

5. Решил  задачу путём сведения к задаче линейного программирования; 

Пересчитал таблицу:

 
 

Пересчитал таблицу:

Нашел оптимальное базисное решение

6. Затем построил  блок схему к задачи с написанием программы и выводом на печать программного кода.
7. Анализом моего результата решения состоит из правил оптимального решения задачи из поставленного условия.

           Порядок работы с симплекс таблицей

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

          Алгоритм перехода к следующей таблице такой:

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

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

Этот коэффициент называется разрешающим, а строка в которой он находится ключевой; в дальнейшем базисная переменная, отвечающая строке разрешающего элемента, должна быть переведена в разряд свободных, а свободная переменная, отвечающая столбцу разрешающего элемента, вводится в число базисных. Строится новая таблица, содержащая новые названия базисных переменных:  разделяем каждый элемент ключевой строки (исключая столбец свободных членов) на разрешающий элемент и полученные значения записываем в строку с измененной базисной переменной новой симплекс таблицы.. Строка разрешающего элемента делится на этот элемент и полученная строка записывается в новую таблицу на то же место в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1. Столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы: В результате получаем новую симплекс-таблицу, отвечающую новому базисному решению. Теперь следует просмотреть строку целевой функции (индексную), если в ней нет отрицательных значений (в задачи на нахождение максимального значения), либо положительных (в задачи на нахождение минимального значения) кроме стоящего на месте  (свободного столбца), то значит, что оптимальное решение получено. В противном случае, переходим к новой симплекс таблице по выше описанному алгоритму. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4. ВЫВОДЫ И РЕКОМЕНДАЦИИ ПО ПРАКТИЧЕСКОМУ ИСПОЛЬЗОВАНИЮ

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

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

Он  основан на пересчёте  коэффициентов в  системе уравнений  и целевой функции  при перемене мест свободной и базисной переменных можно  формализовать и  свести к преобразованию симплекс-таблицы.

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

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

В выводе своего проектирования хочу подвести итог в целом “Решению матричных игр в смешанных стратегиях” .

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

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

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

    По  характеру взаимодействия игры делятся  на:

1)   бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

2)    коалиционные (кооперативные) – могут вступать в коалиции.

    В кооперативных играх коалиции наперёд  определены.

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

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

    Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш  игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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