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

2 –  0 х 0  = 2;   4 – 0 х 0 = 4;  - 6 – (-11) х 0  = - 6 и т.д.

        2                         2                          2 

      Для элементов строки (m +1) проводим контроль правильности вычислений:

Ñ₁ = (11 х 1 + 0 х 0 + 0 х 0) – 11 = 0;  Ñ₂ = (11х 1 + 0  (-2) + 0 х1) – 6 = 5;

Ñ₃ = (11 х 1,5 + 0 х ( - 3,5) + 0 х 1)–9 = 7,5; Ñ₄ = (11х 0 +   0 х 2  + 0 х 4) – 6 =6;

Ñ₅ = (11 х 0,5 + 0 х ( - 1,5) + 0 х 0) – 0 = 5,5; Ñ₆ = (11 х 0 + 0 х 1 + 0 х 0) – 0 =0;

Ñ₇ = (11 х 0 + 0 х 0 + 0 х 1) – 0 = 0; 

      Отсюда  следует, что расчеты выполнены  правильно.

Целевая  функция будет равна:

Z = Ñо = 11 х 10 + 0 х 7 + 0 х 30 = 110 единиц.

План, полученный во второй итерации, не является оптимальным, т.к. в оценочной строке есть один отрицательный  элементÑ₄ = - 6. Следовательно, столбец А₄ – разрешающий столбец. Находим минимальное симплексное отношение:

Q = min   Ао   = min   7   ;  30   = min  (3,5;  7,5) = 3,5

                А₄                2     4 

Минимум принадлежит второй строке, следовательно, она является решающей. Элемент  ₂₄ =2 – разрешающий элемент. Переменная Х₄ вводится в базис вместо переменной Х₆.

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

Целевая функция (III-я итерация):

Z =Ñо =11 х 10 + 6 х 3,5 + 0 х 16 = 131 ден. ед.

Полученный  план не является оптимальным, т.к. в оценочной строке есть 2 отрицательных оценки:

Ñ₂ = - 1 и Ñ₃ = - 3. Сравниваем по модулю, и выбираем максимальную:

ê- 3 ½> ½- 1½® ½- 3½= max

Следовательно, столбец А₃ – разрешающий.

Находим минимальное симплексное  отношение:

Q = min   Ао   = min  10   ;  16  = min   (6,67; 2) = 2

                А₃                1,5     8 

Минимум соответствует 3-1 строке: она будет  разрешающей. Элемент   ₃₃ = 8 – разрешающий. Переменная Х₃ вводится в базис вместо переменной Х₇.

Далее ведется перерасчет элементов таблицы.

Целевая функция (IV-я итерация):

Z =Ñо =11 х 7 + 6 х 7 + 9 х 2 = 137 ден. ед.

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

Этот  план единственный, вырожденный, т.к. переменная Х₂ = 0 (не вошла в базис). Значение целевой функции максимально, и составляет: Z (Х_о) = 137 ден. ед.

Оптимальный план исходной задачи:

Хо = (7; 0; 2; 7) 

2.5 Анализ таблиц.

I-я итерация: Предприятие не использует ресурсы, и не производит продукцию. Остатки ресурсов равны их запасам: балансовые переменные находятся в базисе и Х₅ = 20 ед. ресурса Р_1; Х₆ = 37 ед. ресурса Р_2; Х₇ = 30 ед. ресурса Р_3.  Нет проихзводства и реализации продукции, нет и дохода: Z =Ñо = 0 ден. ед. 

II-я итерация:   Предприятие выпускает только продукцию П₁ в количестве 10 ед. (Х₁ = 10), и получает доход в размере 110 ден. ед. (Z =Ñо = 110). Продукция вида П₂, П₃, П₄ не выпускается, т.к. переменные Х₂, Х₃, Х₄ не вошли в базис.

Сырье Р₁ использовано полностью: Х₅ выведена из базиса. Частично израсходовано сырье Р₂ и его остаток составляет 7 ед. (Х₆ = 7). Сырье Р₃ не используется вообще: Х₇ = 30 ед. не остатке.

      Если  подставить решение данного плана  в систему неравенств (Х₁ = 10; Х₂ = 0; Х₃ = 0; Х₄ = 0), то получим аналогичные выводы: 

2 х 10 + 2 х 0 + 3 х 0 = 20                           20 = 20

3 х 10 + 1 х 0 + 1 х 0 + 2 х 0 = 30               30< 37        (Ñ = 7)

              1 х 0 + 1 х 0 + 4 х 0  = 0                 0 <  30       (Ñ = 30)

Z = 11 х 10 + 6 х 0 + 9 х 0 + 6 х 0 = 110 

III-я итерация:   Предприятие выпускает 2 вида продукции: П₁ в количестве 10 ед. (Х₁ = 10) и П₄ в количестве 3,5 ед. (Х₄ = 3,5). Продукция П₂ и П₃ не производится (Х₂ и Х₄ не вошли в базис).

      Сырье вида Р₁ и Р₂ использовано полностью, т.к. переменные Х₅ и Х₆ выведены из базиса. Сырье Р₃ израсходовано частично, и остаток составляет 16 ед. (Х₇ = 16). При этом доход увеличился, и составляет 131 ден. ед.

      Можно  провести проверку, подставив значения Х₁ = 10; Х₂ = 0; Х₃ = 0; Х₄ = 3,5 в модель задачи. 

IV-я итерация:

Для получения  максимально возможного дохода при  ограниченных ресурсах предприятию  следует выпускать 7 единиц продукции  П₁; 7 единиц продукции П₄ и 2 единицы продукции П₃. Продукцию П₂ к производству не планировать из-за ограниченности ресурсов. При таком плане производства ресурсы вида Р₁ и Р₃ использованы полностью, а остаток ресурса Р₂ составляет всего 2 единицы. Проверка это покажет:

2 х 7 + 2 х 0 + 3 х 2 = 20                           20 = 20

3 х 7 + 1 х 0 + 1 х 2 + 2 х 7 = 35               35< 37        (Ñ = 2)

            1 х 0 + 1 х 2 + 4 х 7  = 30              30 = 30       

      Максимальный  доход составит:

Z max = 11 х 7 + 6 х 0 + 9 х 2 + 6 х 7 = 137 ден. ед. 

ОТ  В Е Т:  Х₁ = 7;  Х₂ = 0;  Х₃ = 2;  Х₄ = 7;

                    Z max = 137 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     ЗАКЛЮЧЕНИЕ

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

     Для достижения поставленной цели на практике рассмотрено решение задачи заданными методами. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

СПИСОК  ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 

1. Абрамов  Л.M., Капустин В.Ф. Математическое программирование. Л., 1981.

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

3. Баумоль  У. Экономическая теория и исследование операций. - М.: Прогресс, 1965.

4. Замков О.О., Толстопятенко АВ., Черемных Ю.И.

5.Исследования операций в экономике: Учеб. пособие для вузов / Под ред. Н.Ш. Кремера – М.: Банки и биржи, 1997. – 407 с.

6. Калихман И.Л. Линейная алгебра и программирование. - М.: Высш. шк.,1967.

7. Капкан А.Б., Майданов А.Д., Царев P.M. Сборник задач по математическому

моделированию экономических процессов на железнодорожном транспорте. -

М: Транспорт, 1978 г.

8. Карасев А.И., Аксютина З.М., Савельева Т.И. Курс высшей математики для экономических вузов. Ч.II. Теория вероятностей и математическое программирование. Линейное программирование: Учеб. пособие для студентов вузов. М.: Высш. школа, 1982.

9. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высш. шк., 1980.- 542 с.

10. Линейное программирование: Учебно-методическое пособие. М.: Изд-во МГУ, 1992.

11. Матвеев В.И., Сагитов Р.В., Шершнев В.Г. Курс линейного программирования для экономистов: Учеб. пособие. - М.: Менеджер, 1998.

12.Математические методы в экономике - М: Издательство "Дис", 1997г

13. Муртаф Б. Современное линейное программирование. - М.: Мир, 1984.

14. Общий курс высшей математики для экономистов: Учебник / Под ред. В.И. Ермакова.  М.: ИНФА-М, 2002. – 434 с.

15.Таха Х. Введение в исследование операций: В 2-х книгах. Кн. I: Пер. с англ. – М.: Мир, 1985. – 479 с.