Курсовая работа: Двойственность в линейном программировании

b_i являются оценками плана двойственной задачи. С_j являются оценками плана исходной задачи.

Найдем решение двойственной задачи по симплексной таблице. В симплексной таблице прописана исходная задача. Также определим оптимальный план двойственной задачи. Также найдем и оптимальный план исходной задачи.

Такой метод принято называть двойственным симплексным методом.

Допустим нужно определить исходную задачу линейного программирования, которая поставлена в общем виде: минимизировать функцию Z=СХ при АХ=A₀ , Х>0. Значит в двойственной задаче следует максимизировать функцию f=YA₀ при YA>С. Пусть определен следующий базис D=(A₁ , А₂ ,…, А_i ,…, А_m ), причем в нем хотя бы одна из компонент вектора Х=D^-1 A₀ =(x₁ , x₂ ,…, x_i ,…, x_m ) отрицательная. Для всех векторов A_j используется следующее соотношение Z_j –C_j >0 (i=1,2,…, n).

Пользуясь теоремой двойственности, Y=С_баз D^-1 является планом двойственной задачи. Этот план не оптимальный. Потому что оценки оптимального плана двойственной задачи должны быть неотрицательными и выбранный базис X содержит отрицательную компоненту и не является планом исходной задачи, а с другой стороны.

Поэтому, следует исключить из базиса исходной задачи вектор А_i , который соответствует компоненте x_i <0. Данный вектор относится к отрицательной оценке, его необходимо включить в базис двойственной задачи.

Просматриваем i-ю строку для выбора вектора, включаемого в базис исходной задачи. Т.е. если строка не имеет x_ij <0, тогда линейная функция двойственной задачи не ограничена на многограннике решений. Поэтому нет решений исходной задачи.

В противном случае для столбцов, имеющих отрицательные значения, определяем q_0j =min(x_i /x_ij )>0. Также находим вектор, который соответствует minq_0j (Z_j –C_j ) при решении исходной задачи на максимум, а также maxq_0j (Z_j –C_j ) при значении исходной задачи на минимум.

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

Допустим, что q_0j =min(x_i /x_ij )=0, т.е. x_i =0, тогда x_ij выбирается как разрешающий элемент, но лишь тогда, когда x_ij >0.

Данный подход к решению задачи не приводит к росту количества отрицательных компонент вектора X. Пока не будет получено Х>0, процесс не прекращается.

Определяя оптимальный план двойственной задачи, находим и оптимальный план исходной задачи.

Используя при решении, алгоритм двойственного симплексного метода условие Z_j –C_j >0 допускается не учитывать, пока не будут исключены все х_i <0.

Обычным симплексным методом определяется оптимальный план. Этот метод обычно используется при условии, что все х_i <0. Чтобы перейти к плану исходной, задачи за одну итерацию надо определить q_0j =max(x_i /x_ij )>0.

Задачи линейного программирования можно решать двойственным симплексным методом. Системы ограничений в задачах при положительном базисе имеют свободные члены любого знака. Двойственный симплексный метод позволяет значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.

2 . Разработка программы

2.1 Постановка задачи

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

Введем следующие обозначения:

i =1,…, m - номера (индексы) используемых ресурсов;

- запас i -го ресурса, т.е. допустимый расход i -го ресурса в плановом периоде; другое название - ограничение по ресурсу i ;

j =1,…, n - номера (индексы) продуктов;

- рыночная цена j -го продукта;

- расход i -го ресурса на производство единицы j -го продукта;

- плановый объем производства j -го продукта, величина неизвестная, ее нужно найти в процессе решения задачи. Исходные данные задачи запишем в виде матрицы.

Рис. 2

Каждая строка матрицы соответствует одному ресурсу, каждый столбец – одному продукту. Справа от каждой строки записана величина ограничения по ресурсу (b ₁ ,…, b_i ,…, b_m ); внизу каждого столбца - цена продуктов (с₁ ,…, с _j ,…, с _m ).

В каждой клеточке матрицы записаны так называемые технологические коэффициенты a_ij , показывающие расход i -го ресурса на производство единицы j -го продукта.