1.5 Решение задачи на пк в пакете simplex

Решив задачу в пакете программ линейной оптимизации SIMPLEX получаем тот же оптимальный план, что и при решении задачи графическим методом (Приложение Б).

1.6 Решение задачи на пк с помощью надстройки поиск решения в среде excel

Результаты решения задачи в Microsoft Excel представлены в приложении В.

Решения, полученные в Microsoft Excel и в пакете программ линейной оптимизации SIMPLEX совпадают.

1.7 Решение задачи симплексным методом вручную

И сходная задача:

0,3х₁ +0,2 х₂ ≤ 200

0,2х₁ + 0.1х₂ ≤ 400

0,1х₁ +0,2 х₂ ≤ 150

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

Каноническая задача:

0 ,3х₁ + 0,2х₂ + х₃ = 200

0,2х₁ + 0,1х₂ + х₄ = 400

0,1х₁ + 0,2х₂ + х₅ = 150

х₂ – х₆ =300

х_j ≥ 0, j = (1,5)

Z = 4х₁ + 6х₂ + 0(–х₃) + 0(–х₄) + 0х₅→min.

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

0 ,3х₁ + 0,2х₂ + х₃ = 200

0,2х₁ + 0,1х₂ + х₄ = 400

0,1х₁ + 0,2х₂ + х₅ = 150

х₂ – х₆ + х₇ =300

х_j ≥ 0, j = (1,7)

Z = 4х₁ + 6х₂ + 0(–х₃) + 0(–х₄) + 0х₅ + Мх₆+Мх₇ → min

Итерация 1

Ш аг 1. Выписываем исходное допустимое базисное решение и соответствующее ему значение целевой функции

х₁ х₂ х₃ х₄ х₅ х₆ х₇

Х₁ = 0 0 200 400 150 0 300

Z₁ = 60*0 + 75*0 + 0*200 +0*400+ 0*150 + 0*0- М *300 = -300М

Шаг 2. Проверим оптимальность полученного решения:

Пусть ∆ х₁ = 1,

тогда ∆ х₃= – 0.3

∆ х₄ = – 0,2

∆ х₅ = – 0,1

∆ Z₁ = 60*1 + 75*0 + 0*(–0,3)+ 0*(-0,2) +0*(-0,1)+0*0-М*0= 60> 0

Вывод по шагу 2: решение Х₁ не оптимальное, переменную х₁ целесообразно ввести в базис, поскольку при этом значение ЦФ увеличивается.

Шаг 3. Определяем какая из прежних базисных переменных должна быть выведена из базиса:

200 : 0,3 = 666,6 (*)

400 : 0,2 = 2000

150 : 0,1 = 1500

Вывод: таким образом, переменная х₁ станет базисной в первом уравнении, прежняя базисная х₃ покидает базис.

Шаг 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных

х ₁ + 2/3 х₂ + 3/10 х₃ = 2000/3

1/30х₂ + 6/100х_{3 .}– х₄ = 800/30

– 4/30х₂ + 3/100х₃ + х₅ = 2500/30

х₂ – х₆ + х₇ =300

Итерация 2

Шаг1. Выписываем очередное допустимое базисное решение и соответствующее ему значение ЦФ:

х₁ х₂ х₃ х₄ х₅ х₆ х₇

Х₂ = 2000/3 0 0 8000/30 2500/30 0 300

Z₂ = 60*2000/3 + 75*0 + 0*0 + 0*8000/30 + 0*2500/30+0*0-М*300 = 40000-300М.

Шаг 2. Проверим оптимальность полученного решения:

Пусть ∆ х₂ = 1,

тогда ∆ х₁ = –2/3

∆ х₄ = –1/30

∆ х₅ = 4/30

∆ х₇ = –1

∆ Z₂ = 60*2/3 + 75*1 + 0*0 + 0*1/30 + 0*(–4/30­­­)+0*0 – М*(-1)=35+М >0

Вывод по шагу 2: переменную х₂ целесообразно ввести в базис т.к. при этом значение целевой функции увеличивается.ь

Шаг 3. Определяем какая из прежних базисных переменных должна быть выведена из базиса.

2000/3 : 2/3 = 1000

2500/30 : 4/30 = 625

300 : 1 = 300 (*)

Вывод по шагу 3: переменная х₂ станет базисной в четвёртом уравнении, прежняя базисная переменная х₇ покинет базис.

Ш аг 4. Пересчет системы линейных уравнений с учетом нового состава базисных переменных

х₁ + 2/3х₆ – 2/3х₇ = 1400/3

+ 6/100 х₃ + х₄ – 1/30 х₆ + 1/30х₇ = 8300/30

+ х₅ + 4/30х₆ – 4/30 х₇ = 1300/30

Х₂ – х₆ + х₇ = 300

Итерация 3

Шаг 1. Выписываем очередное допустимое базисное решение и соответствующее ему значение целевой функции.

х₁ х₂ х₃ х₄ х₅ х₆ х₇

Х₃ = 1400/3 24/5 0 8300/30 1300/30 0 0

Z₃ = 60*1400/3 + 75*300 + 0*0 + 0*8300/30+ 0*1300/30 + 0*0–М*0 = 50500

Шаг 2. Проверяем оптимальность полученного решения

Пусть ∆х₃ = 1,

тогда ∆х₁ = – 3/10

∆х₄ = 6/100

∆х₅= 3/100

∆Z₃ = 60*(-3/10) + 75*0 + 0*1 + 0*6/100 + 0*3/100+0*0–М*0 = – 18 < 0

Вывод по шагу 2: ∆Z₃ < 0 _, переменную х₃ нецелесообразно ввести в базис, поскольку от этого значение целевой функции Z уменьшается.

Шаг 2 продолжается

Пусть ∆ х₆ = 1,

тогда ∆х₁ = –2/3

∆х₄ = 1/30

∆х₅ = –4/30

∆х₂ = 1

∆Z₄ =60*(–2/3) + 75*1 + 0*0+0*1/30+0*(–4/30)+0*0–М*0 = 40 < 0

Вывод по шагу 2: ∆Z₄ < 0 переменную х₆ нецелесообразно ввести в базис т.к. при этом значение целевой функции уменьшается.

Шаг 2 продолжается

Проверяем оптимальность полученного решения

Пусть ∆ х₇ = 1,

тогда ∆х₁ = –2/3

∆х₄ = –1/30

∆х₅ = 4/30

∆х₂ = –1

∆Z₅ =60*2/3 + 75*(–1)+ 0*0+0*1/(–30)+0*4/30+0*0–М*1 = –35 – М < 0

Вывод по шагу 2: ∆Z₅ < 0 переменную х₇ нецелесообразно ввести в базис т.к. при этом значение целевой функции уменьшается.

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