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

  • ID: 17958 
  • 10 страниц

Фрагмент работы:

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

Раздел 1. Решение задач линейного программирования (ЛП).

Построение двойственной задачи ЛП.

Графическое решение прямой задачи ЛП.

Решение задач ЛП (прямой и двойственной) симплекс-методом

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

Графическое решение задачи целочисленного линейного программирования (ЦЛП).

Решение задачи ЦЛП методом ветвей и границ.

Решение задачи о назначениях.

Задание №2. Решение задач нелинейного программирования(НЛП)

Графическое решение условной задачи НЛП.

Решение условной задачи НЛП методом множителей Лагранжа.

Задание 1.

№ 1. Задача ЛП

Z=11x1+13x2®max

[image]

1. Построение двойственной задачи ЛП

Составим двойственную задачу:

[image]

[image]

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

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

(1) 41 - 32 = 36 [image]

(2) 111 + 142 =143 [image]

(3) 1 + 2 = 4 [image]

Построим вектор= (11, 13) и целевую функцию по уравнению 111 + 132 = 0

На рис. 1 видно, что оптимальное решение соответствует точке В, лежащей на пересечении прямых (1) и (2). Поэтому ее координаты находятся как решение системы линейных уравнений, задающих эти прямые:

[image]

При этом значение целевой функции

[image].

[image]

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

3. Решим задачу двойственным симплекс-методом.

Для этого приведем исходную задачу к каноническому виду:

Z=11x1+13x2®max

[image]

За базисные неизвестные примем [image], [image],[image]. Выразим базисные неизвестные и целевую функцию через свободные:

Z=44 +2x2+11x5®max

[image]

Составим симплекс-таблицу:

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