Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Нахождение первого базисного решения






У нас остался открытым вопрос – а как найти первое базисное решение? Вполне может получиться так, что после выражения базисных переменных через свободные мы получим одно из чисел bj отрицательным. Тогда нулевые значения свободных переменных не будут задавать допустимое решение. Данная проблема решается последовательным применением таких же шагов, что и в описанном выше симплекс методе. Мы сначала выбираем любое из уравнений, где свободный член отрицателен. Далее мы в этом уравнении выбираем свободную переменную, при увеличении которой наша базисная переменная будет увеличиваться от bj к нулю. (Возможен и вариант недопустимой задачи, когда в уравнении с отрицательным свободным членом при увеличении любой свободной переменной нужная нам базисная переменная только уменьшается). При увеличении нужной переменной мы также отслеживаем, какая из базисных переменных первая обратится в ноль, и производим пересчет таблицы по алгоритму симплекс-метода. Если первой обратится в ноль та базисная переменная, которую мы увеличиваем, то мы получим новое решение, которое уже будет являться базисным. Если нет, то после пересчета процесс будет повторен сначала.

Рассмотрим пример нахождения базисного решения для задачи: найти максимум целевой функции f=x1+2x2 при ограничениях

Введем дополнительные неотрицательные переменные, чтобы свести задачу к каноническому виду:

Мы можем видеть, что эта система разрешена относительно переменных х3, х4 и х5. Однако, если положить значение свободных переменных равным нулю, то получится решение (0, 0, -1, 3, 3), которое не является допустимым, т.к. значение х3 отрицательно.

Применим описанное выше преобразование системы с целью избавиться от отрицательных свободных членов (такой есть только в первом уравнении). Мы можем увеличить значение базисной переменной х3, увеличивая свободную переменную х2. При этом переменная х5 не препятствует росту х2, а переменная х4 позволяет х2 расти до 3, после чего х4 обратится в 0. Однако, мы замечаем, что нам повезло, и уже при х2=1 переменная х3 сама обратится в 0, поэтому уже после одного шага избавления от отрицательных свободных членов мы получим базисное решение со свободными переменными х1 и х3. Выразив х2 из первого уравнения и подставив во второе, получим систему и соответствующее ей базисное решение (0, 1, 0, 2, 3). В дальнейшем можно действовать по алгоритму симплекс-метода и получить решение задачи.

 

Сформулируем еще одну полезную для практического применения (вторую) теорему двойственности. Для этого введем соответствие между исходными переменными Х и дополнительными переменными У, и, наоборот, между дополнительными переменными Х и исходными переменными У. (дополнительные переменные возникают при сведении общей задачи линейного программирования к канонической). Оказывается, что

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

Содержание лабораторной работы.

1. Ответить на вопросы двух контролирующих программ.

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

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

4. Составить, отладить и протестировать на контрольных примерах программу решения задачи линейного программирования симплекс-методом в среде Excel и на любом из языков программирования. Решить задачу для своего варианта. Учтите, что первое базисное решение может не быть допустимым.

5. Замените ввод данных на чтение из файла и проверьте работу Вашей программы на всех тестах. Файлы данных имеют следующую структуру: в первой строке записано через пробел количество уравнений K и количество неизвестных N. Во второй строке через пробел указываются К номеров базисных переменных. В последующих K строках через пробел записаны по N+1 числу – сначала свободный член соответствующего уравнения, а затем коэффициенты этого уравнения. В последней строке в том же порядке указаны коэффициенты представления целевой функции через переменные.

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

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

Варианты заданий.

Вариант 1

Вид древес. Запасы древ. Шкаф Стенка
прибыль      

Ответ: X = 120 Y = 40 F = 280

 

Вариант 2

Сырье Запасы сырья. А В
прибыль      

Ответ: X = 110 Y = 40 F = 560

 

Вариант 3

Вид оборуд. Количество А В
прибыль      

Ответ: X = 80 Y = 50 F = 750

 

Вариант 4

Вид древес. Запасы древ. Шкаф Стенка
прибыль      

Ответ: X = 90 Y = 80 F = 170

 

Вариант 5

Сырье Запасы сырья А В
прибыль      

Ответ: X = 70 Y = 50 F = 500

 

Вариант 6

Станки t работы станка А В
прибыль      

Ответ: X = 70 Y = 60 F = 200

 

Вариант 7

Вид оборуд. Количество А В
прибыль      

Ответ: X = 110 Y = 60 F = 280

 

Вариант 8

Вид древес. Запасы древ. Шкаф Стенка
прибыль   -  

Ответ: X = 90 Y = 70 F = 910

Вариант 9

Сырьё Запасы сырья А В
прибыль      

Ответ: X = 100 Y = 50 F = 250

 

Вариант 10

Стенки t работы станка А В
прибыль      

Ответ: X = 50 Y = 80 F = 1120

 

Вариант 11

Вид оборуд. Количество А В
прибыль      

Ответ: X = 110 Y = 40 F = 260

 

Вариант 12

Вид древес. Запасы древ. Шкаф Стенка
прибыль      

Ответ: X = 110 Y = 50 F = 750

 

Вариант 13

Сырьё Запасы сырья А В
прибыль      

Ответ: X = 90 Y = 80 F = 920

 

Вариант 14

Станки t работы станка А В
прибыль      

Ответ: X = 100 Y = 30 F = 360

 

Вариант 15

Вид оборуд. Количество А В
прибыль      

Ответ: X = 100 Y = 60 F = 260

 

Вариант 16

Станки t работы станка А В
прибыль      

Ответ: X = 100 Y = 50 F = 650

 

Вариант 17

Станки t работы станка А В
прибыль      

Ответ: X = 80 Y = 50 F = 550

 

Вариант 18

Вид древес. Запасы древ. Шкаф Стенка
прибыль   -  

Ответ: X = 120 Y = 60 F = 300

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.009 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал