Xreferat.com » Рефераты по информатике и программированию » Решение задач линейного программирования

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

Контрольная работа №2


Задание 1


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

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

Индивидуальное задание

Найти максимум и минимум линейной формы графическим методом по исходным данным задачи ЛП (таблица 1).

Таблица 1


Номер варианта Целевая функция Ограничения задачи линейного программирования
6

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

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


Решение задачи

Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых:

x1+4x2=8, 2x1-x2=4, x1+x2­=1,x1=0,x2=0.

Область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 1).


L

Рисунок 1. Графическое решение задачи ЛП


В данной задаче она составляет многоугольник ABCD. Для нахождения экстремума функции Z=-2x1+4x2 , строим разрешающую прямую, приравнивая линейную форму нулю:Z=0. Строим градиент целевой функции C(2;4).

Минимальное значение функция принимает в точке D(4,5;0,7) , а максимальное в точке B.


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


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

Задание 2


Решение задач ЛП симплексным методом с использованием симплекс-таблиц

Цель задания: закрепить теоретические сведения и приобрести практические навыки решения задач ЛП симплекс-методом.

Индивидуальное задание

Найти максимум линейной формы

Z=c1x1+c2x2

при условиях:

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

Данные представлены в таблице 2.


Номер варианта A11 A12 A21 A22 A31 A32 B1 B2 B3 C1 C2
6 4 1 3 6 8 7 43 74 76 7 4

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

Приведем задачу ЛП к каноническому виду:

-Z’= -Z = -7x1 -4x2

при ограничениях

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


x3, x4, x5 — дополнительные переменные.

Во втором уравнении дополнительная переменная введена с коэффициентом -1 и уравнение умножено на -1.

Постановка задачи в виде матрицы системы ограничений

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

Решение задачи ЛП с составленными симплекс-таблицами

Единичные векторы A3, A4, A5 образуют базис трехмерного пространства (m=3). Решать эту задачу алгоритмом симплекс-метода можно, поскольку переменные x3, x4, x5 входят с коэффициентом +1 соответственно в первое, второе и третье ограничения. Таким образом, x3, x4, x5 – базисные переменные, а остальные небазисные. Полагая небазисные переменные в ограничениях равными нулю, получим исходное допустимое базисное решение:

X0=(0,0,43,-74,76).

Заполняем исходную симплекс-таблицу (таблица 2)

Таблица 2. Нулевая симплекс-таблица


i Бx Сб A0 -7 -4 0 0 0 T




A1 A2 A3 A4 A5

Решение задач линейного программирования1

A3 0 43 4 1 1 0 0

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

2 A4 0 74 -3 -6 0 1 0
3 A5 0 76 -8 7 0 0 1
4

0 7 4 0 0 0

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


Так как среди разностей есть положительные, то X0 не является оптимальным решением. Строим новое базисное решение.

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

Выводим из базиса вектор A3,так как

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

Разрешающий элемент таблицы x12 выделим кругом, а разрешающий столбец и строку стрелками.

Таблица 3. Первая симплекс-таблица


i Бx A0 -7 -4 0 0 0 T




A1 A2 A3 A4 A5

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

Решение задач линейного программирования1

A1 -7

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

1

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

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

0 0
2 A4 0

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

0

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

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

1 0
3 A5 0 162 0 9 2 0 1
4

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

0

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

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

0 0

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

Так как среди разностей есть положительные, то оптимальное решение не получено. Строим новое базисное решение.

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

Выводим из базиса вектор A4,так как

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

Таблица 4. Вторая симплекс-таблица


i Бx A0 -7 -4 0 0 0 T




A1 A2 A3 A4 A5
1 A2 -4 43 4 1 4 0 0
2 A4 0 736 21 0

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

1 0
3 A5 0 -225 -36 0 -34 0 1
4

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

-9 0

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

0 0

Так как все разности во второй таблице (таблица 4) неположительны: Решение задач линейного программирования, т получено оптимальное решение:

Решение задач линейного программирования min(-Z)= -225.

Тогда max(Z)= -min(-Z)= 225

Анализ оптимального плана.

Использование переменной x1 нецелесообразно.

Задание 3


Моделирование и решение задач ЛП на ЭВМ


Цель задания: приобрести практические навыки моделирования задач ЛП и их решения симплекс-методом с использованием прикладной программы SIMC.

Индивидуальное задание

Предприятие может работать по 5-ти технологическим процессам, причем кол-во единиц выпускаемой продукции по разным ТП за ед. времени соответственно равны 300, 260, 320, 400, 450 шт. затраты производственных факторов в гривнах при работе по разным ТП в течение 1 ед. времени и располагаемые ресурсы этих факторов в табл.5.

Найти программу максимального выпуска продукции.

Таблица 5.


факторы Способ производства

Ресурсы,

грн


1 2 3 4 5
Сырье 12 15 10 12 11 1300
Эл.энергия 0,2 0,1 0,2 0,25 0,3 30
Зарплата 3 4 5 4 2 400
Накладные расходы 6 5 4 6 4 800

Математическая интерпретация задачи

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

Исходные массивы, записанные в виде, пригодном для решения задачи по программе SIMC

5

4

12.000 15.000 10.000 12.000 11.000 < 1300.000

0.200 0.100 0.200 0.250 0.300 < 30.000

3.000 4.000 5.000 4.000 2.000 < 400.000

6.000 5.000 4.000 6.000 4.000 < 800.000

300.000 260.000 320.000 400.000 450.000

1

Рисунок 2. Исходные массивы для решения задачи


Распечатка ЭВМ с результатом решения


ИТЕРАЦИЯ N=1 РЕШЕНИЕ НАЙДЕНО !!!

ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 5

6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000

7 0.000 30.000 0.200 0.100 0.200 0.250 0.300

8 0.000 400.000 3.000 4.000 5.000 4.000 2.000

9 0.000 800.000 6.000 5.000 4.000 6.000 4.000

0.000 300.000 260.000 320.000 400.000 450.000

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 0.0000


ИТЕРАЦИЯ N=1 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦА ЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 5

6 0.000 1300.000 12.000 15.000 10.000 12.000 11.000

7 0.000 30.000 0.200 0.100 0.200 0.250 0.300

8 0.000 400.000 3.000 4.000 5.000 4.000 2.000

9 0.000 800.000 6.000 5.000 4.000 6.000 4.000

0.000 -300.000 -260.000 -320.000 -400.000 -450.000

В БАЗИС ВВОДИТСЯ 5 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 7 СТОЛБЕЦ

ИТЕРАЦИЯ N=2 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 2 3 4 7

6 0.000 200.000 4.667 11.333 2.667 2.833 -36.667

5 450.000 100.000 0.667 0.333 0.667 0.833 3.333

8 0.000 200.000 1.667 3.333 3.667 2.333 -6.667

9 0.000 400.000 3.333 3.667 1.333 2.667 -13.333

45000.000 -0.000 -110.000 -20.000 -25.000 1500.000

В БАЗИС ВВОДИТСЯ 2 СТОЛБЕЦ

ИЗ БАЗИСА ВЫВОДИТСЯ 6 СТОЛБЕЦ

ИТЕРАЦИЯ N=3 ПРОДОЛЖЕНИЕ РЕШЕНИЯ ТЕКУЩАЯ СИМПЛЕКС-ТАБЛИЦАЗАДАЧА НЕ ВЫРОЖДЕНА

Бx Cб Po 1 3 4 6 7

2 260.000 17.647 0.412 0.235 0.250 0.088 -3.235

5 450.000 94.118 0.529 0.588 0.750 -0.029 4.412

8 0.000 141.176 0.294 2.882 1.500 -0.294 4.118

9 0.000 335.294 1.824 0.471 1.750 -0.324 -1.471

46941.176 45.294 5.882 2.500 9.706 1144.118

КОД ОШИБКИ=0

ОПТИМАЛЬНОЕ ЗНАЧЕНИЕ БАЗИС-ВЕКТОРА И РЕШЕНИЕ

X2=17.6471

X5=94.1176

ОПТИМУМ ЦЕЛЕВОЙ ФУНКЦИИ = 46941.1765

РЕШЕНИЕ НАЙДЕНО !!!

Оптимальный план. Экономическая интерпретация оптимального решения.


В соответствии с полученным результатом выпуск продукции по 1,3 и 4 технологическим процессам нецелесообразен.

Задание 4

Моделирование транспортных задач и их решение методом потенциалов

Цель задания: приобрести практические навыки моделирования и решения транспортной задачи ЛП методом потенциалов.

Индивидуальное задание

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

Таблица 6. 06 вариант транспортной задачи


Вид механизма Себестоимость выполнения единицы работы механизма ,гр. Количество единиц ai механизмов

B1 B2 B3 B4
A1 11 4 3 1 15
A2 6 8 9 7 10
A3 4 8 4 2 35
Потребности bj участков в механизмах 25 20 10 5

Математическая формулировка транспортной задачи


Пусть xij – количество единиц работы, выполненной механизмом вида ai, на участке работы bj.Требуется определить план распределения механизмов, минимизирующий себестоимость выполнения всей работы:

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

при ограничениях:

1) Решение задач линейного программирования; - все механизмы должны быть задействованы;

2)Решение задач линейного программирования; - все участки должны быть загружены;

3) Решение задач линейного программирования; - количество единиц работы не может быть отрицательным

Условие разрешимости задачи выполняется:

25+20+10+5=15+10+35; 60=60.

Исходный опорный план, составленный по методу северо-западного угла

Таблица 7


I
ai

B1 B2 B3 B4
A1 11

4

15

3 1 15
A2

6

5

8

5

9


7


10
A3

4

20

8

4

10

2

5

35
bj 25 20 10 5

Решение транспортной задачи методом потенциалов


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

Итак, видно что в число занятых клеток следует ввести клетку (2,1).

Получим новый улучшенный план – таблица 8.

Таблица 8


I
ai

B1 B2 B3 B4
A1

11


4

15

3


1


15
A2

6

5

8

5

9


7


10
A3

4

20

8

4

10

5

5

35
bj 25 20 10 5

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

Введём в число занятых клетку (1,4) . Получим новый улучшенный план – Таблица 9.

Таблица 9


I
ai

B1 B2 B3 B4
A1

11


4

10

3

5

1


15
A2

6


8

10

9


7


10
A3

4

25

8

4

5

2

5

35
bj 25 20 10 5

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

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

x12=15; x­21=5; x22=5; x­31=20;x33=10; x­34=5.

Z=15*4+5*6+5*8+20*4+10*4+5*2=260.

Анализ оптимального плана

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

Задание 5


Решение транспортной задачи на ЭВМ

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

Индивидуальное задание:

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

Таблица 10. 06 вариант транспортной задачи


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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
-->

Похожие рефераты: