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

                                 Z-0 (x1, x2, x3) = 3X₁ + 7X₂ + 2X₃ → max  
 

Введем дополнительные переменные X₄, X₅ . Введем искусственную переменную R₁. 
Z-0=3X₁+7X₂+2X₃-M·R₁ à (max) 
 

Преобразуем первое ограничение:

X_i≥0 
Получили задачу:

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

  X₂ +  X₃ + R₁ = 8

  X₁+2X₂ +X₅ = 24

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

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

    Приведем  задачу к канонической форме.

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

    Требуется найти вектор , доставляющий максимум линейной форме

                  

при условиях

                  

                   

     где

Решим задачу симплекс-методом

Строим начальную  симплекс-таблицу:

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

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке 0-Z есть отрицательные элементы, то полученное решение не оптимально. Для определения ведущего столбца найдем максимальный по модулю отрицательный элемент в строке 0-Z (-3). А ведущая строка та, у которой наименьшее положительное отношение свободного члена к соответствующему элементу ведущего столбца. 
 
 

Тогда каноническую форму задачи ЛП можно представить  в следующем матричном виде эквивалентном  первоначальному:

Z=CX →max,

AX=B,

X≥0.

где 0 - нулевая матрица-столбец той же размерности, что и матрица X.

Замечание.

Не ограничивая  общности, можно полагать, что свободные  члены неотрицательны, т.е. b i ≥ 0, где i =¯1,m (иначе ограничительные уравнения можно умножить на (-1)). 
Пересчитаем таблицу

 
Эта таблица является последней, по ней читаем ответ задачи.

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

При котором Z max = 233/4= 58,25  

План производства:

X₁ =3/4= 0,75; X₂ = 8; X₃ = 0; X₄ = 3;   X₅ =29/4= 7,25;   R₁ = 8;   M = 0

Соответственно по решению, вычисляем:

Z= 3*0,75+7*8+2*0+3+7,25-0*8= 2,25+56+0+10,25-0 = 58,25+10,25-0 = 68,5-0 = 68,5 ≈ 69

Z= 69 ден. ед. 

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

Блок-схемы основных процедур при решении  и программировании задач

Алгоритм программы  →   Рис. 1.        ↓

 

 

 

 
 
 

  

 

 

 

 

 
 

 
 

 

 

Рисунок 1 –Алгоритм  программы для решения ЗЛП (частный случай) 

Программа к поставленной задачи (код  программы)

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

Программа определяет:

План выпуска продукции для получения максимальной прибыли.  

        1. Описание работы программы, листинг программы 

1.1 Обоснование выбора  языка

Программа для  решения данной задачи составлена на языке C++.C++ представляет собой систему программирования. Как любая подобная система,C++ предназначена для разработки программ и имеет две характерные особенности: создаваемые с ее помощью программы могут работать не только под управлением Windows,но и в системе MS-DOS.

C++ представляет собой наиболее полный пакет объектно-ориентированного программирования. Язык прост в применении и базируется на C#,что упрощает создание программ, людям, знакомым с данным языком.   

1.2 Описание работы  программы

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

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

Программа выводит  данные в строку F/  

3. Листинг программы

//----------------------------------------------------------------------------------------------

     #include <stdio.h>

     #include <string.h>

     #include <math.h> 
 

     #define PRECISION  "%6.2f" // формат вывода дробных чисел

     #define PRECISION2  "%.2f" // он же только целая часть любой длины 

     #define MAXDIGIT 1000000 // должно быть очень большое число (больше всех) 

     typedef enum

     {

           NEXT_ITERATION,  // нужно продолжать итерации

           PLAN_OPTIMAL,  // найден оптимальный опорный план

           ODR_BREAK,   // ОДР разомкнута

           ODR_EMPTY,   // ОДР пустая

           DUAL_DONE   /* первый этап (построение опорного плана) окончен,

                                   переходим к поиску оптим.оп.плана (обычный Симплекс) */

<