Изучение методов решения задач линейного программирования

Федеральное государственное автономное

образовательное учреждение

высшего профессионального образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Институт цветных металлов и материаловедения

Кафедра автоматизации производственных процессов

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №1

Вариант 2

Преподаватель                                                                               Г.Б. Даныкина

Студент      МФ 07-08                                                                    И.В. Большаков

Красноярск 2011

               Цель работы: изучить методы решения задач линейного программирования; приобрести навыки разработки моделей линейного программирования и решения задач на ЭВМ.

          Исходные данные для выполнения работы приведены в таблице 1.

      Таблица 1 – Исходные данные

          1 Решение графическим методом

          Выразим x₂ из условий ограничений:

1)  x₁ + 2·x₂ ≤ 12             2) 3·x₁ + 2·x₂ ≥ 8           3) –2·x₁ + x₂ ≥ –8  

                x₂ = 6 – 0,5·x                   x₂ = 4 – 1,5·x₁                       x₂ = 2·x₁ – 8

          Задаваясь значениями x₁ построим графики ограничений (рисунок 1)

          Построим график целевой функции G (рисунок 1) и определим ее градиент. Для этого приравняем выражение x₁ + 3·x₂  к константе и выразим x₂.

–2·x₁ + 3·x₂ = 0,

Рисунок 1 – Допустимая область задачи

          Сместим прямую в точку пересечения графиков (1) и оси х₂ согласно направлению вектора. Полученная точка с координатами х₁ = 0 и х₂ = 6 будет оптимальным решением данной задачи. Значение целевой функции в данной точке равно

G = –2·x₁ + 3·x₂,

G = 0 + 3·6,

G = 18.

          2 Решение симплекс – методом линейного программирования

          Приведем задачу к канонической форме: минимизировать функцию

G = 2·x₁ – 3·x₂

          при следующих ограничениях:

          Начальное базисное решение представлено в таблице 2

Таблица 2 – Начальное базисное решение

Базисные переменные						Постоянные
	х1                      х2                     х3                     х4                      х5
х3	1	2	1	0	0	12
х4	3	2	0	-1	0	8
х5	2	-1	0	0	1	8
- строка	2	-3	0	0	0	G = 0

          Так как относительная оценка c₂ отрицательна, необходимо перейти к смежному базисному решению. В качестве новой базисной переменной принимаем x₂, поскольку эта небазисная переменная имеет наибольшую (по модулю) относительную оценку.

          Минимальное отношение достигается в уравнении, содержащем базисную переменную x₄, т.е. она первой среди базисных переменных обратится в ноль, и поэтому выводится из базиса.  В результате базисными переменными становятся x₃, x₂ и x₅. Смежное базисное решение представлено в таблице 3.

Таблица 3 – Смежное базисное решение

Базисные переменные						Постоянные
	х1                    х2                       х3                      х4                        х5
х3	-2	0	1	1	0	4
х2	1,5	1	0	-0,5	0	4
х5	3,5	0	0	-0,5	1	12
- строка	6,5	0	0	-1,5	0	G = -12

          Относительная оценка c₄ отрицательна, значит оптимальное решение еще не достигнуто. Для продолжения поиска определяем ведущую переменную.

Минимальное отношение достигается в уравнении, содержащем базисную переменную x₃, т.е. она первой среди базисных переменных обратится в нуль, и поэтому выводится из базиса.  В результате базисными переменными становятся x₄, x₂ и x₅. Второе смежное базисное решение представлено в таблице 4.

Таблица 4 – Второе смежное базисное решение

Базисные переменные						Постоянные
	х1                    х2                       х3                      х4                        х5
х4	-2	0	1	1	0	4
х2	0,5	1	0,5	0	0	6
х5	2,5	0	0,5	0	1	14
- строка	3,5	0	1,5	0	0	G = -18

          Относительные оценки все положительные, следовательно оптимальное решение достигнуто. При этом получены следующие значения: х₁ = 0, х₂ = 6, х₃ = 0, х₄ = 4, х₅ = 14, G = -18.

          3 Решение задачи линейного программирования в программе Microsoft Excel.

          Расчетная таблица:

          Поиск решения:

          Параметры поиска решения:

          Полученное оптимальное решение:

          То есть: х₁ = 0, х₂ = 6 и G = 18.

          Вывод: Изучили методы решения задач линейного программирования, результаты по всем 3-м способам совпали, следовательно, все шаги были выполнено верно и оптимальным решением данной задачи является значения х₁ = 0, х₂ = 6 и при этом критерий оптимальности G = 18.